# Second-Order Guarantees of Stochastic Gradient Descent in Non-Convex Optimization

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

## Key facts

- Cited by 11 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 19 Aug 2019.

## Built on by (most cited first, 11 of 11)

- [SGD with a Constant Large Learning Rate Can Converge to Local Maxima](https://mlsanity.com/paper/2107.11774/) (2021)
- [Type-II Saddles and Probabilistic Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2303.13093/) (2023)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [Distributed Adaptive Learning Under Communication Constraints](https://mlsanity.com/paper/2112.02129/) (2021)
- [On the Trade-off between Flatness and Optimization in Distributed Learning](https://mlsanity.com/paper/2406.20006/) (2024)
- [Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumption](https://mlsanity.com/paper/2302.07862/) (2023)
- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (2025)
- [3DPG: Distributed Deep Deterministic Policy Gradient Algorithms for Networked Multi-Agent Systems](https://mlsanity.com/paper/2201.00570/) (2022)
- [Exact Subspace Diffusion for Decentralized Multitask Learning](https://mlsanity.com/paper/2304.07358/) (2023)
- [On the Escaping Efficiency of Distributed Adversarial Training Algorithms](https://mlsanity.com/paper/2509.11337/) (2025)
- [On the Oracle Complexity of Interpolation-Based Gradient Descent](https://mlsanity.com/paper/2606.19878/) (2026)

## Abstract (arXiv)

Recent years have seen increased interest in performance guarantees of gradient descent algorithms for non-convex optimization. A number of works have uncovered that gradient noise plays a critical role in the ability of gradient descent recursions to efficiently escape saddle-points and reach second-order stationary points. Most available works limit the gradient noise component to be bounded with probability one or sub-Gaussian and leverage concentration inequalities to arrive at high-probability results. We present an alternate approach, relying primarily on mean-square arguments and show that a more relaxed relative bound on the gradient noise variance is sufficient to ensure efficient escape from saddle-points without the need to inject additional noise, employ alternating step-sizes or rely on a global dispersive noise assumption, as long as a gradient noise component is present in a descent direction for every saddle-point.