mlsanityData to 7 Oct 2026

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

arXiv 2006.11144 ↗First posted 19 Jun 2020math.OC cs.LG math.PRcited by 79

Not on the map. Why?

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.

Key facts. Cited by 79 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 15; 2023: 15; 2024: 11; 2025: 15; 2026: 9.

79 papers.

Sort:

  1. 2023Tackling the Curse of Dimensionality with Physics-Informed Neural Networkscited by 78
  2. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 38
  3. 2021Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responsescited by 32
  4. 2022On Almost Sure Convergence Rates of Stochastic Gradient Methodscited by 32
  5. 2021Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapescited by 27
  6. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  7. 2021Convergence of gradient descent for learning linear neural networkscited by 22
  8. 2022A unified stochastic approximation framework for learning in gamescited by 22
  9. 2022Neural Tangent Kernel: A Surveycited by 22
  10. 2022Monte Carlo PINNs: deep learning approach for forward and inverse problems involving high dimensional fractional partial differential equationscited by 20
  11. 2021Global Convergence and Stability of Stochastic Gradient Descentcited by 17
  12. 2023FedRC: Tackling Diverse Distribution Shifts Challenge in Federated Learning by Robust Clusteringcited by 15
38 more
  1. 2021Turning Channel Noise into an Accelerator for Over-the-Air Principal Component Analysiscited by 13
  2. 2022A Unified Convergence Theorem for Stochastic Optimization Methodscited by 12
  3. 2021Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterizationcited by 10
  4. 2021SGD with a Constant Large Learning Rate Can Converge to Local Maximacited by 8
  5. 2023Type-II Saddles and Probabilistic Stability of Stochastic Gradient Descentcited by 8
  6. 2023Riemannian stochastic optimization methods avoid strict saddle pointscited by 8
  7. 2025ODE approximation for the Adam algorithm: General and overparametrized settingcited by 8
  8. 2024Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetrycited by 7
  9. 2022Metrizing Fairnesscited by 6
  10. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
  11. 2023On the existence of minimizers in shallow residual ReLU neural network optimization landscapescited by 6
  12. 2024Nesterov acceleration in benignly non-convex landscapescited by 6
  13. 2023On the existence of optimal shallow feedforward networks with ReLU activationcited by 5
  14. 2023High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariancecited by 5
  15. 2024Almost sure convergence rates of stochastic gradient methods under gradient dominationcited by 5
  16. 2022Scalable Set Encoding with Universal Mini-Batch Consistency and Unbiased Full Set Gradient Approximationcited by 4
  17. 2023Fed-QSSL: A Framework for Personalized Federated Learning under Bitwidth and Data Heterogeneitycited by 4
  18. 2025Online Decision-Focused Learningcited by 4
  19. 2025Actionable Interpretability via Causal Hypergraphs: Unravelling Batch Size Effects in Deep Learningcited by 4
  20. 2023Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networkscited by 3
  21. 2023Learning Unorthogonalized Matrices for Rotation Estimationcited by 3
  22. 2024Federated reinforcement learning for robot motion planning with zero-shot generalizationcited by 3
  23. 2024Optimal time sampling in physics-informed neural networkscited by 3
  24. 2025Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularizationcited by 3
  25. 2025Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrizationcited by 3
  26. 2021Inertial Newton Algorithms Avoiding Strict Saddle Pointscited by 2
  27. 2022On Uniform Boundedness Properties of SGD and its Momentum Variantscited by 2
  28. 2022Weak Convergence of Approximate reflection coupling and its Application to Non-convex Optimizationcited by 2
  29. 2023Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updatingcited by 2
  30. 2024Convergence of a L2 regularized Policy Gradient Algorithm for the Multi Armed Banditcited by 2
  31. 2025Statistical Inference for Online Algorithmscited by 2
  32. 2025Statistical Guarantees for High-Dimensional Stochastic Gradient Descentcited by 2
  33. 2021Stochastic Subgradient Descent on a Generic Definable Function Converges to a Minimizercited by 1
  34. 2023Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumptioncited by 1
  35. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  36. 2024Uncertainty quantification by block bootstrap for differentially private stochastic gradient descentcited by 1
  37. 2025FedDAA: Dynamic Client Clustering for Concept Drift Adaptation in Federated Learningcited by 1
  38. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1

50 most cited of 79 All 79 (JSON)