mlsanityData to 7 Oct 2026

On Almost Sure Convergence Rates of Stochastic Gradient Methods

arXiv 2202.04295 ↗First posted 9 Feb 2022cs.LG math.OCcited by 32

Not on the map. Why?

Abstract (arXiv)

The vast majority of convergence rates analysis for stochastic gradient methods in the literature focus on convergence in expectation, whereas trajectory-wise almost sure convergence is clearly important to ensure that any instantiation of the stochastic algorithms would converge with probability one. Here we provide a unified almost sure convergence rates analysis for stochastic gradient descent (SGD), stochastic heavy-ball (SHB), and stochastic Nesterov's accelerated gradient (SNAG) methods. We show, for the first time, that the almost sure convergence rates obtained for these stochastic gradient methods on strongly convex functions, are arbitrarily close to their optimal convergence rates possible. For non-convex objective functions, we not only show that a weighted average of the squared gradient norms converges to zero almost surely, but also the last iterates of the algorithms. We further provide last-iterate almost sure convergence rates analysis for stochastic gradient methods on weakly convex smooth functions, in contrast with most existing results in the literature that only provide convergence in expectation for a weighted average of the iterates.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Builds on 16 of its 42 references that are in the map. First posted on arXiv 9 Feb 2022.

Builds on

16 of 42 references.

References · 16

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  3. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  4. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 94
  5. 2020On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problemscited by 79
  6. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 60
  7. 2018A Unified Analysis of Stochastic Momentum Methods for Deep Learningcited by 54
  8. 2016Stochastic Heavy Ballcited by 40
  9. 2016Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimizationcited by 34
  10. 2020Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimizationcited by 32
  11. 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
  12. 2013Stochastic Majorization-Minimization Algorithms for Large-Scale Optimizationcited by 28
4 more
  1. 2016A Lyapunov Analysis of Momentum Methods in Optimizationcited by 28
  2. 2020On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settingscited by 27
  3. 2019Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descentcited by 13
  4. 2019The Role of Memory in Stochastic Optimizationcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 11; 2024: 4; 2025: 8; 2026: 7.

32 papers.

Sort:

  1. 2023Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneitycited by 64
  2. 2023Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applicationscited by 15
  3. 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Casecited by 13
  4. 2023Practical and Matching Gradient Variance Bounds for Black-Box Variational Bayesian Inferencecited by 6
  5. 2022Emergent specialization from participation dynamics and multi-learner retrainingcited by 5
  6. 2023High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariancecited by 5
  7. 2024Almost sure convergence rates of stochastic gradient methods under gradient dominationcited by 5
  8. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  9. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 5
  10. 2024A quantitative Robbins-Siegmund theoremcited by 4
  11. 2023Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updatingcited by 2
  12. 2023The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learningcited by 2
20 more
  1. 2023From Optimization to Control: Quasi Policy Iterationcited by 2
  2. 2025Statistical Inference for Online Algorithmscited by 2
  3. 2025Convergence of Stochastic Gradient Methods for Wide Two-Layer Physics-Informed Neural Networks for the Poisson Equationcited by 2
  4. 2026High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noisecited by 2
  5. 2023Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumptioncited by 1
  6. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  7. 2024On the SAGA algorithm with decreasing stepcited by 1
  8. 2025Consensus-based optimization for closed-box adversarial attacks and a connection to evolution strategiescited by 1
  9. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  10. 2022Convergence of Batch Updating Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Resultscited by 0
  11. 2023Stability and Convergence of Distributed Stochastic Approximations with large Unbounded Stochastic Information Delayscited by 0
  12. 2024Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimizationcited by 0
  13. 2025Convergence of Momentum-Based Optimization Algorithms with Time-Varying Parameterscited by 0
  14. 2025Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methodscited by 0
  15. 2026Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Gamescited by 0
  16. 2026Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approachcited by 0
  17. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  18. 2026Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithmcited by 0
  19. 2026Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noisecited by 0
  20. 2026Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Boundscited by 0