# Gradient Descent Can Take Exponential Time to Escape Saddle Points

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

## Key facts

- Cited by 74 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2017.

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

- [Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances](https://mlsanity.com/paper/2105.12221/) (2021)
- [Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity](https://mlsanity.com/paper/2106.15933/) (2021)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Stochastic Training is Not Necessary for Generalization](https://mlsanity.com/paper/2109.14119/) (2021)
- [Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifold](https://mlsanity.com/paper/2209.09211/) (2022)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [LoRA Training in the NTK Regime has No Spurious Local Minima](https://mlsanity.com/paper/2402.11867/) (2024)
- [Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscape](https://mlsanity.com/paper/2402.01258/) (2024)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Small Batch Size Training for Language Models: When Vanilla SGD Works, and Why Gradient Accumulation Is Wasteful](https://mlsanity.com/paper/2507.07101/) (2025)
- [Taxonomizing local versus global structure in neural network loss landscapes](https://mlsanity.com/paper/2107.11228/) (2021)
- [Overparameterization of deep ResNet: zero loss and mean-field analysis](https://mlsanity.com/paper/2105.14417/) (2021)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [spred: Solving L1 Penalty with SGD](https://mlsanity.com/paper/2210.01212/) (2022)
- [Stochastic noise can be helpful for variational quantum algorithms](https://mlsanity.com/paper/2210.06723/) (2022)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Stability Analysis of Sharpness-Aware Minimization](https://mlsanity.com/paper/2301.06308/) (2023)
- [Mask in the Mirror: Implicit Sparsification](https://mlsanity.com/paper/2408.09966/) (2024)
- [On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regime](https://mlsanity.com/paper/2110.02926/) (2021)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [On a continuous time model of gradient descent dynamics and instability in deep learning](https://mlsanity.com/paper/2302.01952/) (2023)
- [Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices](https://mlsanity.com/paper/2105.10360/) (2021)
- [Special Properties of Gradient Descent with Large Learning Rates](https://mlsanity.com/paper/2205.15142/) (2022)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy](https://mlsanity.com/paper/2212.07534/) (2022)
- [Exploring the Effect of Multi-step Ascent in Sharpness-Aware Minimization](https://mlsanity.com/paper/2302.10181/) (2023)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [SGD with a Constant Large Learning Rate Can Converge to Local Maxima](https://mlsanity.com/paper/2107.11774/) (2021)

## Abstract (arXiv)

Although gradient descent (GD) almost always escapes saddle points asymptotically [Lee et al., 2016], this paper shows that even with fairly natural random initialization schemes and non-pathological functions, GD can be significantly slowed down by saddle points, taking exponential time to escape. On the other hand, gradient descent with perturbations [Ge et al., 2015, Jin et al., 2017] is not slowed down by saddle points - it can find an approximate local minimizer in polynomial time. This result implies that GD is inherently slower than perturbed GD, and justifies the importance of adding perturbations for efficient non-convex optimization. While our focus is theoretical, we also present experiments that illustrate our theoretical findings.