An Alternative View: When Does SGD Escape Local Minima?

By Robert D. Kleinberg, Yuanzhi Li, Yang Yuan. 2018

349 citations recorded by the source corpus.

Stochastic gradient descent (SGD) is widely used in machine learning. Although being commonly viewed as a fast but not accurate version of gradient descent (GD), it always finds better solutions than GD for modern neural networks. In order to understand this phenomenon, we take an alternative view that SGD is working on the convolved (thus smoothed) version of the loss function. We show that, even if the function $f$ has many bad local minima or saddle points, as long as for every point $x$, the weighted average of the gradients of its neighborhoods is one point convex with respect to the desired solution $x^*$, SGD will get close to, and then stay around $x^*$ with constant probability. More specifically, SGD will not get stuck at "sharp" local minima with small diameters, as long as the neighborhoods of these regions contain enough gradient information. The neighborhood size is controlled by step size and gradient noise. Our result identifies a set of functions that SGD provably works, which is much larger than the set of convex functions. Empirically, we observe that the loss surface of neural networks enjoys nice one point convexity properties locally, therefore our theorem helps explain why SGD works so well for neural networks.

Subfields: 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 Optimization & Training

Citations in the corpus

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “important class of non-convex functions [16, 40, 44, 78, 79] satisfying the restricted secant inequality (RSI).”
A Little Is Enough: Circumventing Defenses For Distributed Learning (2019, background): “This last assumption is advocated by the fact that SGD better converges with a little random noise [21, 25, 13].”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “These include neural networks [18, 17, 35], matrix completion [36] and phase retrieval [6].”
AlterSGD: Finding Flat Minima for Continual Learning by Alternative Training (2021, background): “One of the solutions for mitigating the distribution variation problem is to seek the ﬂat-minimal region in the loss landscape [22, 11, 24, 21], as illustrated in Figure 2.”
Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, background): “…tuning: There are two beneﬁts: (1) the policies found in the perturbed game may not remain an equilibrium in the original game, so ﬁne-tuning ensures convergence; (2) in practice, ﬁne-tuning could further help escape a suboptimal mode via the noise in PG (Ge et al., 2015; Kleinberg et al., 2018).”
An Empirical Study of Example Forgetting during Deep Neural Network Learning (2018, background): “generalization of deep neural networks (Zhang et al., 2016) have been offered: ﬂat minima generalize better and stochastic gradient descent converges towards them (Hochreiter & Schmidhuber, 1997; Kleinberg et al., 2018), gradient descent protects against overﬁtting (Advani & Saxe, 2017; Tach”
Shakedrop Regularization for Deep Residual Learning (2018, background): “SGD and weight decay are commonly used techniques in the training of deep neural networks.”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “Thus, the additional smoothing in the algorithm might not be needed by an observation in [30].”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “It has also been observed empirically that neural networks satisfy the PL condition [6].”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “Prior works prove that stochastic gradient descent provably convergences to an approximate local optimum (Ge et al., 2015; Sun et al., 2015; Lee et al., 2017; Kleinberg et al., 2018).”
Linear Convergence of Adaptive Stochastic Gradient Descent (2019, background): “The Assumption (A1b) is a generally well-known condition satisfied by a wide range of non-convex optimization problems including over-parameterized neural networks (Soltanolkotabi et al., 2019; Kleinberg et al., 2018; Li and Yuan, 2017; Vaswani et al., 2018; Wu et al., 2019).”
On the Learning Dynamics of Deep Neural Networks (2018, background): “…flatness of minima and generalization (Hochreiter & Schmidhuber, 1997), natural convergence of stochastic gradient descent towards such minima (Kleinberg et al., 2018), built-in hierarchical representations (LeCun et al., 2015), gradient descent naturally protecting against overfitting…”
The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games (2021, background): “We hypothesize that mini-batching in this scenario helps escape a poor local optimum, similar to phenomena observed in the supervised learning setting (Kleinberg et al., 2018).”
Surrogate modeling for fluid flows based on physics-constrained deep learning without simulation data (2019, background): “The SGD algorithms are known to work very well to escape bad local minima in the neural network training [63] under one point convexity property.”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, background): “Indeed, a similar assumption (for the non-convex minimization problem) has been made for analyzing the convergence of stochastic gradient descent for learning neural networks [45] and also was observed in practice [42].”
When Vision Transformers Outperform ResNets without Pretraining or Strong Data Augmentations (2021, methodology): “It has been extensively studied that the convergence to a ﬂat region whose curvature is small beneﬁts the generalization of neural networks (Keskar et al., 2017; Kleinberg et al., 2018; Jastrz˛ebski et al., 2019; Chen & Hsieh, 2020; Smith & Le, 2018; Zela et al., 2020; Chaudhari et al., 2017).”