# Escaping Saddles with Stochastic Gradients

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

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2018.

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

- [Positive-Negative Momentum: Manipulating Stochastic Gradient Noise to Improve Generalization](https://mlsanity.com/paper/2103.17182/) (2021)
- [Escaping Saddle Points for Effective Generalization on Class-Imbalanced Data](https://mlsanity.com/paper/2212.13827/) (2022)
- [The loss landscape of deep linear neural networks: a second-order analysis](https://mlsanity.com/paper/2107.13289/) (2021)
- [An SDE for Modeling SAM: Theory and Insights](https://mlsanity.com/paper/2301.08203/) (2023)
- [A Theoretical Analysis of the Learning Dynamics under Class Imbalance](https://mlsanity.com/paper/2207.00391/) (2022)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [On the Overlooked Structure of Stochastic Gradients](https://mlsanity.com/paper/2212.02083/) (2022)
- [How to escape sharp minima with random perturbations](https://mlsanity.com/paper/2305.15659/) (2023)
- [A Global Geometric Analysis of Maximal Coding Rate Reduction](https://mlsanity.com/paper/2406.01909/) (2024)
- [On the different regimes of Stochastic Gradient Descent](https://mlsanity.com/paper/2309.10688/) (2023)
- [FlashSinkhorn: IO-Aware Entropic Optimal Transport on GPU](https://mlsanity.com/paper/2602.03067/) (2026)
- [Provable Super-Convergence with a Large Cyclical Learning Rate](https://mlsanity.com/paper/2102.10734/) (2021)
- [Special Properties of Gradient Descent with Large Learning Rates](https://mlsanity.com/paper/2205.15142/) (2022)
- [Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy](https://mlsanity.com/paper/2212.07534/) (2022)
- [A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descent](https://mlsanity.com/paper/2310.00692/) (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)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Passage-Mask: A Learnable Regularization Strategy for Retriever-Reader Models](https://mlsanity.com/paper/2211.00915/) (2022)
- [Loss Landscape of Shallow ReLU-like Neural Networks: Stationary Points, Saddle Escape, and Network Embedding](https://mlsanity.com/paper/2402.05626/) (2024)
- [On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updates](https://mlsanity.com/paper/2106.07094/) (2021)
- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [Exponential escape efficiency of SGD from sharp minima in non-stationary regime](https://mlsanity.com/paper/2111.04004/) (2021)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [On the Theoretical Properties of Noise Correlation in Stochastic Optimization](https://mlsanity.com/paper/2209.09162/) (2022)
- [Efficient displacement convex optimization with particle gradient descent](https://mlsanity.com/paper/2302.04753/) (2023)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [Concurrent Training and Layer Pruning of Deep Neural Networks](https://mlsanity.com/paper/2406.04549/) (2024)
- [Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms](https://mlsanity.com/paper/2102.02837/) (2021)

## Abstract (arXiv)

We analyze the variance of stochastic gradients along negative curvature directions in certain non-convex machine learning models and show that stochastic gradients exhibit a strong component along these directions. Furthermore, we show that - contrary to the case of isotropic noise - this variance is proportional to the magnitude of the corresponding eigenvalues and not decreasing in the dimensionality. Based upon this observation we propose a new assumption under which we show that the injection of explicit, isotropic noise usually applied to make gradient descent escape saddle points can successfully be replaced by a simple SGD step. Additionally - and under the same condition - we derive the first convergence rate for plain SGD to a second-order stationary point in a number of iterations that is independent of the problem dimension.