mlsanityData to 7 Oct 2026

Almost sure convergence rates of stochastic gradient methods under gradient domination

arXiv 2405.13592 ↗First posted 22 May 2024cs.LG math.OCcited by 5

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient methods are among the most important algorithms in training machine learning problems. While classical assumptions such as strong convexity allow a simple analysis they are rarely satisfied in applications. In recent years, global and local gradient domination properties have shown to be a more realistic replacement of strong convexity. They were proved to hold in diverse settings such as (simple) policy gradient methods in reinforcement learning and training of deep neural networks with analytic activation functions. We prove almost sure convergence rates f(Xn)-f^*∈ obig( n^-frac14β-1+εbig) of the last iterate for stochastic gradient descent (with and without momentum) under global and local β-gradient domination assumptions. The almost sure rates get arbitrarily close to recent rates in expectation. Finally, we demonstrate how to apply our results to the training task in both supervised and reinforcement learning.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 38 of its 65 references that are in the map. First posted on arXiv 22 May 2024.

Builds on

38 of 65 references.

References · 38

  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. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  5. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  6. 2017Bridging the Gap Between Value and Policy Based Reinforcement Learningcited by 178
  7. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  8. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  9. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  10. 2020On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problemscited by 79
  11. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  12. 2019Convergence rates for the stochastic gradient descent method for non-convex objective functionscited by 66
26 more
  1. 2018A Unified Analysis of Stochastic Momentum Methods for Deep Learningcited by 54
  2. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  3. 2019Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptionscited by 48
  4. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  5. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  6. 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
  7. 2016Stochastic Heavy Ballcited by 40
  8. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 38
  9. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 35
  10. 2016Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimizationcited by 34
  11. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 34
  12. 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
  13. 2020Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimizationcited by 32
  14. 2022On Almost Sure Convergence Rates of Stochastic Gradient Methodscited by 32
  15. 2020High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noisecited by 31
  16. 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
  17. 2021Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapescited by 27
  18. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  19. 2022Convergence of gradient descent for deep neural networkscited by 24
  20. 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
  21. 2022Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequalitycited by 19
  22. 2023High Probability Convergence of Clipped-SGD Under Heavy-tailed Noisecited by 19
  23. 2019The Role of Memory in Stochastic Optimizationcited by 10
  24. 2023Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodscited by 9
  25. 2018Convergence of Cubic Regularization for Nonconvex Optimization under KL Propertycited by 8
  26. 2019Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functionscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 1.

5 papers.

  1. 2025On Entropy Control in LLM-RL Algorithmscited by 39
  2. 2024Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequalitycited by 2
  3. 2024Stochastic Gradient Descent Revisitedcited by 0
  4. 2025Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemescited by 0
  5. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0