Gradient Descent Converges to Minimizers

By Jason D. Lee, Max Simchowitz, Michael I. Jordan, B. Recht. 2016

218 citations recorded by the source corpus.

We show that gradient descent converges to a local minimizer, almost surely with random initialization. This is proved by applying the Stable Manifold Theorem from dynamical systems theory.

Subfields: Artificial Intelligence, Modeling and Simulation, Statistics and Probability

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

In Modeling and Simulation

In Statistics and Probability

Citations in the corpus

Learning explanations that are hard to vary (2020, background): “Under some standard technical assumptions [Lee et al., 2016], (θkGD)k≥0 converges to a parameter GD∞(θ0) := limk→∞ θkGD, which is a local minimizer of L, with probability one2.”
No bad local minima: Data independent training error guarantees for multilayer neural networks (2016, background): “However, SGD is only guaranteed to converge to critical points in which the gradient of the expected loss is zero [5], and, speciﬁcally, to stable local minima [25] (this is true also for regular gradient descent [22]).”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “ovably work in this setting include cubic regularization [36], trust region methods [16], approximate cubic regularization schemes [3,12,13], randomly initialized and perturbed (stochastic) gradients [22,17,29,30,22]. Therefore, the above theorem demonstrates that a weight matrix with small training”
Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond (2016, background): “One such step has been taken in Panageas & Piliouras (2016) in relaxing the isolated singularity condition that was assumed in Lee et al. (2016).”
Topology and Geometry of Half-Rectified Network Optimization (2016, positive): “Other authors have advocated that the real danger in high-dimensional setups are saddle points rather than poor local minima [3], although recent results rigorously establish that gradient descent does not get stuck on saddle points [12] but merely slowed down.”
The Mechanics of n-Player Differentiable Games (2018, methodology): “Gradient-based methods can reliably ﬁnd local – but not global – optima of nonconvex objective functions (Lee et al., 2016; 2017).”
Exponentially vanishing sub-optimal local minima in multilayer neural networks (2017, background): “SGD is only guaranteed to converge to critical points in which the gradient of the expected loss is zero (Bottou, 1998), and, speciﬁcally, to local minima (Pemantle, 1990) (this is true also for regular gradient descent (Lee et al., 2016)).”
Gradient Descent Learns Linear Dynamical Systems (2016, background): “It is known that under certain mild conditions (stochastic) gradient descent converges even on non-convex functions to local minimum [GHJY15, LSJR16].”
Stochastic Heavy ball (2016, methodology): “This geometrical result is also used in [LSJR16].”
Local Saddle Point Optimization: A Curvature Exploitation Approach (2018, unknown): “We start with a lemma extending known results for general minimization problems that prove that gradient descent with random initialization almost surely converges to a stable stationary point [22].”
Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks (2019, background): “It has been proven that gradient descent can ﬁnd global minima [Ge et al., 2015, Lee et al., 2016] if the loss surface satisﬁes: (1) all local minima are global and (2) all saddle points are strict in the sense that there exists at least one negative curvature direction.”
Comparing dynamics: deep neural networks versus glassy systems (2018, background): “Several other works, including Lee et al. (2016), claim that gradient-based training avoids such obstacles even if they do exist.”
Empirical Analysis of the Hessian of Over-Parametrized Neural Networks (2017, background): “Recently Lee et al. [2016] showed that they indeed converge to minimizers.”
Improving Generalization Performance by Switching from Adam to SGD (2017, background): “This includes, but is not limited to, guarantees of saddle point avoidance (Lee et al., 2016), improved generalization (Hardt et al., 2015; Wilson et al., 2017) and interpretations as Bayesian inference (Mandt et al., 2017).”
Implicit Geometric Regularization for Learning Shapes (2020, background): “This is in contrast to the proof of Theorem 2 that uses the result of (Lee et al., 2016) building upon the discrete nature of gradient descent iterations.”
Topology and Geometry of Deep Rectified Network Optimization Landscapes (2016, unknown): “01 54 0v 1 [ st”