# Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

arXiv: https://arxiv.org/abs/1711.10456 · HTML: https://mlsanity.com/paper/1711.10456/

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2017.

## Built on by (most cited first, 30 of 66)

- [Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models](https://mlsanity.com/paper/2208.06677/) (2022)
- [Muon Optimizes Under Spectral Norm Constraints](https://mlsanity.com/paper/2506.15054/) (2025)
- [ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction](https://mlsanity.com/paper/2105.10446/) (2021)
- [Cautious Optimizers: Improving Training with One Line of Code](https://mlsanity.com/paper/2411.16085/) (2024)
- [The loss landscape of deep linear neural networks: a second-order analysis](https://mlsanity.com/paper/2107.13289/) (2021)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Accelerating Inexact HyperGradient Descent for Bilevel Optimization](https://mlsanity.com/paper/2307.00126/) (2023)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks](https://mlsanity.com/paper/2403.05293/) (2024)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Differentially Private Temporal Difference Learning with Stochastic Nonconvex-Strongly-Concave Optimization](https://mlsanity.com/paper/2201.10447/) (2022)
- [Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods](https://mlsanity.com/paper/2412.02175/) (2024)
- [For Manifold Learning, Deep Neural Networks can be Locality Sensitive Hash Functions](https://mlsanity.com/paper/2103.06875/) (2021)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms](https://mlsanity.com/paper/2102.02837/) (2021)
- [Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning](https://mlsanity.com/paper/2310.11897/) (2023)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)
- [Grams: Gradient Descent with Adaptive Momentum Scaling](https://mlsanity.com/paper/2412.17107/) (2024)
- [On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport](https://mlsanity.com/paper/2109.15030/) (2021)
- [An Adaptive Gradient Method with Energy and Momentum](https://mlsanity.com/paper/2203.12191/) (2022)
- [Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism](https://mlsanity.com/paper/2510.03167/) (2025)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)
- [Tackling benign nonconvexity with smoothing and stochastic gradients](https://mlsanity.com/paper/2202.09052/) (2022)
- [A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees](https://mlsanity.com/paper/2207.05697/) (2022)

## Abstract (arXiv)

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 tildeO(1/ε7/4) iterations, faster than the tildeO(1/ε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.