Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

By Chi Jin, Praneeth Netrapalli, Michael I. Jordan. 2017

294 citations recorded by the source corpus.

Nesterov's accelerated gradient descent (AGD), an instance of the general family of "momentum methods", provably achieves faster convergence rate than gradient descent (GD) in the convex setting. However, whether these methods are superior to GD in the nonconvex setting remains open. This paper studies a simple variant of AGD, and shows that it escapes saddle points and finds a second-order stationary point in $\tilde{O}(1/\epsilon^{7/4})$ iterations, faster than the $\tilde{O}(1/\epsilon^{2})$ iterations required by GD. To the best of our knowledge, this is the first Hessian-free algorithm to find a second-order stationary point faster than GD, and also the first single-loop algorithm with a faster rate than GD even in the setting of finding a first-order stationary point. Our analysis is based on two key ideas: (1) the use of a simple Hamiltonian function, inspired by a continuous-time perspective, which AGD monotonically decreases per step even for nonconvex functions, and (2) a novel framework called improve or localize, which is useful for tracking the long-term behavior of gradient-based optimization algorithms. We believe that these techniques may deepen our understanding of both acceleration algorithms and nonconvex optimization.

Subfields: Artificial Intelligence, Computational Mechanics, Genetics

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 Genetics

Citations in the corpus

Learning explanations that are hard to vary (2020, methodology): “, 2018, Kushner and Yin, 2003], momentum [Jin et al., 2017], and adaptive methods including Adam [Barakat and Bianchi, 2019] and Adagrad [Ward et al.”
signSGD: compressed optimisation for non-convex problems (2018, background): “Existing theoretical analyses of momentum often rely on the absence of gradient stochasticity (e.g. Jin et al. (2017)) or convexity (e.g. Goh (2017)) to show that momentum’s asymptotic convergence rate can beat gradient descent.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Specifically, [178] proposed a perturbed version of Nesterov’s accelerated gradient descent (AGD), which adds perturbation to AGD and combines it with an operation similar to Negative-Curvature-Descent described above.”
Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models (2022, background): “Below, we ﬁrst introduce the key motivation of Adan in Section III-A, and then give detailed algorithmic steps in Section III-B.”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “Other algorithms are developed for general non-convex optimization, and they can be classiﬁed into gradient-based [27, 44, 68, 4, 5, 33], Hessian-vector-product-based [12, 2, 56, 57], and Hessian-based [54, 19] methods.”
On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization (2018, background): “Recently, certain accelerated version of perturbed gradient descent (PAGD) algorithm is also proposed in [25], which shows the fastest convergence rate among all Hessian free algorithms.”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, methodology): “Recently, several studies have explored AG methods for non-convex optimization [15, 19, 3, 12].”
Exponential convergence rates for Batch Normalization: The power of length-direction decoupling in non-convex optimization (2018, unknown): “Agd Smoothness O(Tgd −7/4 log(1/ )) Sublinear (Jin et al., 2017) Agd Smoothness+convexity O(Tgd −1) Sublinear (Nesterov, 2013)”
A high-bias, low-variance introduction to Machine Learning for physicists (2018, unknown): “The details of these boosted method are beyond the scope of this review, and we refer avid readers to (Jin et al., 2017) for details.”
Stochastic Heavy ball (2016, result): “Beyond the natural exploration of the state space ability of the HBF, the recent work [JNJ17] has also investigated the escape properties of another second order stochastic algorithms with inertia and has shown the ease of stochastic accelerated gradient descent to escape from local minimizers faste”
Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity (2019, background): “…work, much theoretical progress was made to accelerate different variations of the original smooth convex problems (e.g. Ghadimi and Lan, 2016; 2012; Beck and Teboulle, 2009; Shalev-Shwartz and Zhang, 2014; Jin et al., 2018; Carmon et al., 2018; Allen-Zhu, 2017; Lin et al., 2015; Nesterov, 2012).”
Asymmetric Valleys: Beyond Sharp and Flat Local Minima (2019, background): “For example, it is shown that they could escape saddle points or sharp local minima under reasonable assumptions (Ge et al., 2015; Jin et al., 2017; 2018a;b; Xu et al., 2018; Allen-Zhu, 2018a;b; Allen-Zhu & Li, 2018; Kleinberg et al., 2018).”
Convergence Guarantees for RMSProp and ADAM in Non-Convex Optimization and an Empirical Comparison to Nesterov Acceleration (2018, methodology): “Momentum methods like HB and NAG have been shown to have superior convergence properties compared to gradient descent in the deterministic setting both for convex and non-convex functions [29, 33, 48, 30, 31, 16].”
Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, background): “Finally, there is a growing body of first-order algorithms that explicitly include additional negative curvature steps to derive state-of-the-art time complexities in classical minimization problems [4, 66, 14, 40] as well as in min-max problems to avoid convergence to unstructured saddle points [1]”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “We emphasize that Assumptions 1, 2, and 3 are standard for non-convex stochastic optimization (Agarwal et al., 2017; Carmon et al., 2017b; Jin et al., 2017a; Xu et al., 2017; Allen-Zhu & Li, 2018).”
Escaping Saddles with Stochastic Gradients (2018, methodology): “Based upon this observations, recent works prove second-order convergence of normalized GD (Levy, 2016) and perturbed GD (Jin et al., 2017a).”