Timezone: »

 
Oral
Stability and Generalization of Learning Algorithms that Converge to Global Optima
Zachary Charles · Dimitris Papailiopoulos

Wed Jul 11 04:50 AM -- 05:10 AM (PDT) @ A6
in Statistical Learning Theory 2 »

We establish novel generalization bounds for learning algorithms that converge to global minima. We derive black-box stability results that only depend on the convergence of a learning algorithm and the geometry around the minimizers of the empirical risk function. The results are shown for non-convex loss functions satisfying the Polyak-Lojasiewicz (PL) and the quadratic growth (QG) conditions, which we show arise for 1-layer neural networks with leaky ReLU activations and deep neural networks with linear activations. We use our results to establish the stability of first-order methods such as stochastic gradient descent (SGD), gradient descent (GD), randomized coordinate descent (RCD), and the stochastic variance reduced gradient method (SVRG), in both the PL and the strongly convex setting. Our results match or improve state-of-the-art generalization bounds and can easily extend to similar optimization algorithms. Finally, although our results imply comparable stability for SGD and GD in the PL setting, we show that there exist simple quadratic models with multiple local minima where SGD is stable but GD is not.

[ PDF]  [ Video] 

Author Information

Zachary Charles (University of Wisconsin-Madison)
Dimitris Papailiopoulos (ECE at University of Wisconsin-Madison)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors