# Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2019.

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

- [Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models](https://mlsanity.com/paper/2208.06677/) (2022)
- [Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training](https://mlsanity.com/paper/2101.12699/) (2021)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)](https://mlsanity.com/paper/2102.12470/) (2021)
- [The Dynamics of Sharpness-Aware Minimization: Bouncing Across Ravines and Drifting Towards Wide Minima](https://mlsanity.com/paper/2210.01513/) (2022)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [Random Scaling and Momentum for Non-smooth Non-convex Optimization](https://mlsanity.com/paper/2405.09742/) (2024)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [Global Convergence and Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2110.01663/) (2021)
- [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)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Special Properties of Gradient Descent with Large Learning Rates](https://mlsanity.com/paper/2205.15142/) (2022)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms](https://mlsanity.com/paper/2102.02837/) (2021)
- [Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition](https://mlsanity.com/paper/2210.00346/) (2022)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)
- [Vanishing Curvature and the Power of Adaptive Methods in Randomly Initialized Deep Networks](https://mlsanity.com/paper/2106.03763/) (2021)
- [Second-Order Convergence in Private Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2505.15647/) (2025)
- [Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism](https://mlsanity.com/paper/2510.03167/) (2025)
- [Tackling benign nonconvexity with smoothing and stochastic gradients](https://mlsanity.com/paper/2202.09052/) (2022)
- [Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?](https://mlsanity.com/paper/2302.10963/) (2023)
- [Escaping Saddle Points with Compressed SGD](https://mlsanity.com/paper/2105.10090/) (2021)
- [Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumption](https://mlsanity.com/paper/2302.07862/) (2023)
- [SiGeo: Sub-One-Shot NAS via Information Theory and Geometry of Loss Landscape](https://mlsanity.com/paper/2311.13169/) (2023)

## Abstract (arXiv)

In this paper, we give a sharp analysis for Stochastic Gradient Descent (SGD) and prove that SGD is able to efficiently escape from saddle points and find an (ε, O(ε0.5))-approximate second-order stationary point in tildeO(ε-3.5) stochastic gradient computations for generic nonconvex optimization problems, when the objective function satisfies gradient-Lipschitz, Hessian-Lipschitz, and dispersive noise assumptions. This result subverts the classical belief that SGD requires at least O(ε-4) stochastic gradient computations for obtaining an (ε,O(ε0.5))-approximate second-order stationary point. Such SGD rate matches, up to a polylogarithmic factor of problem-dependent parameters, the rate of most accelerated nonconvex stochastic optimization algorithms that adopt additional techniques, such as Nesterov's momentum acceleration, negative curvature search, as well as quadratic and cubic regularization tricks. Our novel analysis gives new insights into nonconvex SGD and can be potentially generalized to a broad class of stochastic optimization algorithms.