# On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems

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

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2020.

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

- [Tackling the Curse of Dimensionality with Physics-Informed Neural Networks](https://mlsanity.com/paper/2307.12306/) (2023)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses](https://mlsanity.com/paper/2107.05762/) (2021)
- [Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes](https://mlsanity.com/paper/2102.09385/) (2021)
- [Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2110.10117/) (2021)
- [A unified stochastic approximation framework for learning in games](https://mlsanity.com/paper/2206.03922/) (2022)
- [Neural Tangent Kernel: A Survey](https://mlsanity.com/paper/2208.13614/) (2022)
- [Convergence of gradient descent for learning linear neural networks](https://mlsanity.com/paper/2108.02040/) (2021)
- [Monte Carlo PINNs: deep learning approach for forward and inverse problems involving high dimensional fractional partial differential equations](https://mlsanity.com/paper/2203.08501/) (2022)
- [Global Convergence and Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2110.01663/) (2021)
- [FedRC: Tackling Diverse Distribution Shifts Challenge in Federated Learning by Robust Clustering](https://mlsanity.com/paper/2301.12379/) (2023)
- [Turning Channel Noise into an Accelerator for Over-the-Air Principal Component Analysis](https://mlsanity.com/paper/2104.10095/) (2021)
- [Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization](https://mlsanity.com/paper/2111.06328/) (2021)
- [A Unified Convergence Theorem for Stochastic Optimization Methods](https://mlsanity.com/paper/2206.03907/) (2022)
- [ODE approximation for the Adam algorithm: General and overparametrized setting](https://mlsanity.com/paper/2511.04622/) (2025)
- [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)
- [Riemannian stochastic optimization methods avoid strict saddle points](https://mlsanity.com/paper/2311.02374/) (2023)
- [Nesterov acceleration in benignly non-convex landscapes](https://mlsanity.com/paper/2410.08395/) (2024)
- [Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry](https://mlsanity.com/paper/2410.15637/) (2024)
- [Metrizing Fairness](https://mlsanity.com/paper/2205.15049/) (2022)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [On the existence of minimizers in shallow residual ReLU neural network optimization landscapes](https://mlsanity.com/paper/2302.14690/) (2023)
- [High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance](https://mlsanity.com/paper/2304.00707/) (2023)
- [On the existence of optimal shallow feedforward networks with ReLU activation](https://mlsanity.com/paper/2303.03950/) (2023)
- [Almost sure convergence rates of stochastic gradient methods under gradient domination](https://mlsanity.com/paper/2405.13592/) (2024)
- [Scalable Set Encoding with Universal Mini-Batch Consistency and Unbiased Full Set Gradient Approximation](https://mlsanity.com/paper/2208.12401/) (2022)
- [Fed-QSSL: A Framework for Personalized Federated Learning under Bitwidth and Data Heterogeneity](https://mlsanity.com/paper/2312.13380/) (2023)
- [Online Decision-Focused Learning](https://mlsanity.com/paper/2505.13564/) (2025)

## Abstract (arXiv)

This paper analyzes the trajectories of stochastic gradient descent (SGD) to help understand the algorithm's convergence properties in non-convex problems. We first show that the sequence of iterates generated by SGD remains bounded and converges with probability 1 under a very broad range of step-size schedules. Subsequently, going beyond existing positive probability guarantees, we show that SGD avoids strict saddle points/manifolds with probability 1 for the entire spectrum of step-size policies considered. Finally, we prove that the algorithm's rate of convergence to Hurwicz minimizers is O(1/np) if the method is employed with a Theta(1/np) step-size schedule. This provides an important guideline for tuning the algorithm's step-size as it suggests that a cool-down phase with a vanishing step-size could lead to faster convergence; we demonstrate this heuristic using ResNet architectures on CIFAR.