# Almost sure convergence rates of stochastic gradient methods under gradient domination

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 38 of its 65 references that are in the map.
- First posted on arXiv 22 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 38)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Bridging the Gap Between Value and Policy Based Reinforcement Learning](https://mlsanity.com/paper/1702.08892/) (2017)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [Convergence rates for the stochastic gradient descent method for non-convex objective functions](https://mlsanity.com/paper/1904.01517/) (2019)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [A Unified Analysis of Stochastic Momentum Methods for Deep Learning](https://mlsanity.com/paper/1808.10396/) (2018)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions](https://mlsanity.com/paper/1902.00908/) (2019)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2312.08531/) (2023)
- [Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization](https://mlsanity.com/paper/1604.03257/) (2016)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [On exponential convergence of SGD in non-convex over-parametrized learning](https://mlsanity.com/paper/1811.02564/) (2018)
- [Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization](https://mlsanity.com/paper/2002.05466/) (2020)
- [High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise](https://mlsanity.com/paper/2006.05610/) (2020)
- [New Convergence Aspects of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1811.12403/) (2018)
- [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)

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

- [On Entropy Control in LLM-RL Algorithms](https://mlsanity.com/paper/2509.03493/) (2025)
- [Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality](https://mlsanity.com/paper/2410.16849/) (2024)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [Stochastic Gradient Descent Revisited](https://mlsanity.com/paper/2412.06070/) (2024)
- [Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemes](https://mlsanity.com/paper/2507.07281/) (2025)

## 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.