mlsanityData to 7 Oct 2026

Gradient Descent Can Take Exponential Time to Escape Saddle Points

arXiv 1705.10412 ↗First posted 29 May 2017math.OC cs.LG stat.MLcited by 74

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 21; 2022: 21; 2023: 12; 2024: 13; 2025: 3; 2026: 4.

74 papers.

Sort:

  1. 2021Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariancescited by 125
  2. 2021Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsitycited by 83
  3. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  4. 2023Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneitycited by 64
  5. 2021Stochastic Training is Not Necessary for Generalizationcited by 63
  6. 2022Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifoldcited by 50
  7. 2024LoRA Training in the NTK Regime has No Spurious Local Minimacited by 48
  8. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  9. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  10. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 43
  11. 2025Small Batch Size Training for Language Models: When Vanilla SGD Works, and Why Gradient Accumulation Is Wastefulcited by 36
  12. 2021Taxonomizing local versus global structure in neural network loss landscapescited by 34
38 more
  1. 2021Overparameterization of deep ResNet: zero loss and mean-field analysiscited by 24
  2. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  3. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  4. 2022spred: Solving L1 Penalty with SGDcited by 16
  5. 2022Stochastic noise can be helpful for variational quantum algorithmscited by 16
  6. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  7. 2023Stability Analysis of Sharpness-Aware Minimizationcited by 14
  8. 2024Mask in the Mirror: Implicit Sparsificationcited by 12
  9. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  10. 2023On a continuous time model of gradient descent dynamics and instability in deep learningcited by 11
  11. 2021Multi-source Learning via Completion of Block-wise Overlapping Noisy Matricescited by 10
  12. 2021On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regimecited by 10
  13. 2022Special Properties of Gradient Descent with Large Learning Ratescited by 10
  14. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  15. 2022Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracycited by 10
  16. 2023Exploring the Effect of Multi-step Ascent in Sharpness-Aware Minimizationcited by 9
  17. 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
  18. 2021SGD with a Constant Large Learning Rate Can Converge to Local Maximacited by 8
  19. 2024Stabilizing Sharpness-aware Minimization Through A Simple Renormalization Strategycited by 8
  20. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  21. 2025Hardness of Learning Fixed Parities with Neural Networkscited by 7
  22. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  23. 2024Nesterov acceleration in benignly non-convex landscapescited by 6
  24. 2021On the Second-order Convergence Properties of Random Search Methodscited by 5
  25. 2022Gradient descent provably escapes saddle points in the training of shallow ReLU networkscited by 5
  26. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  27. 2022On the Theoretical Properties of Noise Correlation in Stochastic Optimizationcited by 5
  28. 2023Efficient displacement convex optimization with particle gradient descentcited by 5
  29. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
  30. 2022Rank-1 Matrix Completion with Gradient Descent and Small Random Initializationcited by 4
  31. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  32. 2023Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compressioncited by 4
  33. 2021Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resiliencecited by 3
  34. 2021Vanishing Curvature and the Power of Adaptive Methods in Randomly Initialized Deep Networkscited by 3
  35. 2022Gradient Descent, Stochastic Optimization, and Other Talescited by 3
  36. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
  37. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  38. 2022Losing momentum in continuous-time stochastic optimisationcited by 2

50 most cited of 74 All 74 (JSON)