How to Escape Saddle Points Efficiently

By Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, Michael I. Jordan. 2017

945 citations recorded by the source corpus.

This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The convergence rate of this procedure matches the well-known convergence rate of gradient descent to first-order stationary points, up to log factors. When all saddle points are non-degenerate, all second-order stationary points are local minima, and our result thus shows that perturbed gradient descent can escape saddle points almost for free. Our results can be directly applied to many machine learning applications, including deep learning. As a particular concrete example of such an application, we show that our results can be used directly to establish sharp global convergence rates for matrix factorization. Our results rely on a novel characterization of the geometry around saddle points, which may be of independent interest to the non-convex optimization community.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

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 Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

An Alternative View: When Does SGD Escape Local Minima? (2018, background): “For example, it is proved that noise helps to escape saddle points [7, 16], gives better generalization [9, 23], and also guarantees polynomial hitting time of good local minima under some assumptions [29].”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “This experiments also shows that the optimization of neural networks is less sensitive to gradient noises, and the noises within a certain range may even help the algorithm to avoid bad local minimums [14].”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “The hope is to leverage recent advance in first-order algorithms (Ge et al., 2015; Lee et al., 2016; Jin et al., 2017) which showed that if the landscape satisfies (1) all local minima are global and (2) all saddle points are strict (i.”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “For this function class, researchers have shown (perturbed) gradient descent (Jin et al., 2017; Ge et al., 2015; Lee et al., 2016; Du et al., 2017a) can find a global minimum.”
Online Meta-Learning (2019, neutral): “As-sumption 1.3 is a statement about the higher order smoothness of functions which is common in non-convex analysis (Nesterov & Polyak, 2006; Jin et al., 2017).”
Few-Shot Learning via Learning the Representation, Provably (2020, background): “Therefore, randomly initialized gradient descent or perturbed gradient descent are guaranteed to converge to a global minimum of (16) in polynomial-time (Ge et al., 2015, Lee et al., 2016, Jin et al., 2017).”
Learning One-hidden-layer Neural Networks with Landscape Design (2017, methodology): “These allow us to use straightforward stochastic gradient descent (see guarantees in [GHJY15, JGN + 17]) to optimize G ( ) and converge to a local minimum, which is also a global minimum (Corollary 2.4).”
How to Start Training: The Effect of Initialization and Architecture (2018, background): “…distinguish two kinds: problems that prevent a given neural network from ever achieving better-than-chance performance and problems that have to do with later stages of training, such as escaping ﬂat regions and saddle points [12, 27], reaching spurious local minima [5, 15], and overﬁtting [2, 34].”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, methodology): “No spurious local minmum, i.e., all local minima are global, then perturbed (stochastic) gradient descent [Ge et al., 2015, Jin et al., 2017, Levy, 2016] or methods with second order information [Nesterov and Polyak, 2006, Curtis et al., 2014, Carmon et al., 2016, Allen-Zhu, 2017] can ﬁnd a global…”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, methodology): “The NEON is inspired by the perturbed gradient descent (PGD) method (a method for solving deterministic non-convex problems) proposed in the seminal work [11] and its connection with the Power method as discussed shortly.”
Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization (2018, background): “However, recent work shows that random perturbations ensure that gradient ascent quickly escapes saddle points and ﬁnds an approximate local optimum (Jin et al. 2017).”
Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator (2018, result): “Similarly, one may hope that recent results on escaping saddle points (Nesterov & Polyak, 2006; Ge et al., 2015; Jin et al., 2017) immediately imply that gradient descent converges quickly to the global optima, due to that there are no (spurious) local optima.”
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, methodology): “The proof of this lemma is mostly calculations (and observing the fact that when U , V are both very large, the gradient will essentially point to 0 ), as an example this is done for matrix factorization in [Jin et al., 2017].”
Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks (2019, background): “Combining with existing advances in gradient descent avoiding saddle-points (Ge et al., 2015; Lee et al., 2016; Jin et al., 2017), these show that gradient descent ﬁnd the global minimum.”