On exponential convergence of SGD in non-convex over-parametrized learning

By Raef Bassily, Mikhail Belkin, Siyuan Ma. 2018

112 citations recorded by the source corpus.

Large over-parametrized models learned via stochastic gradient descent (SGD) methods have become a key element in modern machine learning. Although SGD methods are very effective in practice, most theoretical analyses of SGD suggest slower convergence than what is empirically observed. In our recent work [8] we analyzed how interpolation, common in modern over-parametrized learning, results in exponential convergence of SGD with constant step size for convex loss functions. In this note, we extend those results to a much broader non-convex function class satisfying the Polyak-Lojasiewicz (PL) condition. A number of important non-convex problems in machine learning, including some classes of neural networks, have been recently shown to satisfy the PL condition. We argue that the PL condition provides a relevant and attractive setting for many machine learning problems, particularly in the over-parametrized regime.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Simon Lacoste-Julien
2. Peter Richtárik
3. Gauthier Gidel
4. Stefano Soatto
5. Francis R. Bach
6. Nicolas Loizou
7. Sharan Vaswani
8. Mark W. Schmidt

In Computational Mechanics

1. Simon Lacoste-Julien
2. Peter Richtárik
3. Gauthier Gidel
4. Sharan Vaswani
5. Francis R. Bach
6. Mark W. Schmidt
7. Nicolas Loizou
8. Issam Hadj Laradji

In Statistics and Probability

1. Simon Lacoste-Julien
2. Gauthier Gidel
3. Samet Oymak
4. M. Soltanolkotabi
5. Alessandro Achille
6. Mark W. Schmidt
7. Sharan Vaswani
8. Issam Hadj Laradji

In Optimization & Training

1. Simon Lacoste-Julien
2. Peter Richtárik
3. Sharan Vaswani
4. Gauthier Gidel
5. Issam Hadj Laradji
6. Nicolas Loizou
7. Mark W. Schmidt
8. Francis R. Bach

Citations in the corpus

• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, background): “Interpolation allows stochastic first-order methods to attain the convergence rates of their deterministic counterparts, without the need for explicit variance reduction (Vaswani et al., 2019a,b; Ma et al., 2018; Bassily et al., 2018).”
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Theorem 5.”
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “[3], who considered minimizing non-convex functions satisfying the Polyak-Lojasiewicz [28] (PL) inequality (a generalization of strong-convexity) under the interpolation condition.”
• Mixed-Privacy Forgetting in Deep Networks (2020, methodology): “[4] Raef Bassily, Mikhail Belkin, and Siyuan Ma.”
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks (2020, background): “The paper [4] proved fast convergence of stochastic gradient descent with constant step size for over-parameterized models, while [29] refined this result showing SGD convergence within a ball with a certain radius.”
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path? (2018, background): “PL condition is particularly suited for analyzing overparameterized problems and has been utilized by several recent papers (Bassily et al., 2018; Karimi et al., 2016; Lei et al., 2017; Ma et al., 2017; Vaswani et al., 2018).”