mlsanityData to 14 Oct 2026

How to Escape Saddle Points Efficiently

arXiv 1703.00887 ↗First posted 2 Mar 2017cs.LG math.OC stat.MLcited by 285

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 285 papers in the map (data through 14 Oct 2026). First posted on arXiv 2 Mar 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 62; 2022: 62; 2023: 51; 2024: 42; 2025: 28; 2026: 40.

285 papers.

Sort:

By area:

  1. 20243D Gaussian Splatting as Markov Chain Monte Carlocited by 217
  2. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 128
  3. 2021Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariancescited by 127
  4. 2021Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applicationscited by 97
  5. 2022Understanding Contrastive Learning Requires Incorporating Inductive Biasescited by 96
  6. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  7. 2021Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsitycited by 85
  8. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
  9. 2021On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)cited by 73
  10. 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
  11. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  12. 2021iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradientscited by 51
38 more
  1. 2022Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifoldcited by 50
  2. 2024LoRA Training in the NTK Regime has No Spurious Local Minimacited by 48
  3. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 46
  4. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 45
  5. 2021On Tilted Losses in Machine Learning: Theory and Applicationscited by 43
  6. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  7. 2021Taxonomizing local versus global structure in neural network loss landscapescited by 34
  8. 2023Optimal Transport for Treatment Effect Estimationcited by 32
  9. 2024On-the-fly Modulation for Balanced Multimodal Learningcited by 32
  10. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 31
  11. 2021Positive-Negative Momentum: Manipulating Stochastic Gradient Noise to Improve Generalizationcited by 28
  12. 2022Escaping Saddle Points for Effective Generalization on Class-Imbalanced Datacited by 28
  13. 2022Explicit Regularization in Overparametrized Models via Noise Injectioncited by 26
  14. 2021Overparameterization of deep ResNet: zero loss and mean-field analysiscited by 24
  15. 2021The loss landscape of deep linear neural networks: a second-order analysiscited by 24
  16. 2022Convergence of gradient descent for deep neural networkscited by 24
  17. 2024MENTOR: Mixture-of-Experts Network with Task-Oriented Perturbation for Visual Reinforcement Learningcited by 23
  18. 2023An SDE for Modeling SAM: Theory and Insightscited by 22
  19. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  20. 2022A Theoretical Analysis of the Learning Dynamics under Class Imbalancecited by 20
  21. 2021Noether: The More Things Change, the More Stay the Samecited by 19
  22. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 19
  23. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  24. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  25. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  26. 2022spred: Solving L1 Penalty with SGDcited by 17
  27. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 17
  28. 2021Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalizationcited by 16
  29. 2022BEINIT: Avoiding Barren Plateaus in Variational Quantum Algorithmscited by 16
  30. 2024Automatically Adaptive Conformal Risk Controlcited by 16
  31. 2021Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorizationcited by 15
  32. 2023Accelerating Inexact HyperGradient Descent for Bilevel Optimizationcited by 15
  33. 2021Lazy OCO: Online Convex Optimization on a Switching Budgetcited by 14
  34. 2021Turning Channel Noise into an Accelerator for Over-the-Air Principal Component Analysiscited by 14
  35. 2021AutoLRS: Automatic Learning-Rate Schedule by Bayesian Optimization on the Flycited by 14
  36. 2021Smooth Bilevel Programming for Sparse Regularizationcited by 14
  37. 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Casecited by 14
  38. 2023Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregressioncited by 14

50 most cited of 285 All 285 (JSON)