# Revisiting Step-Size Assumptions in Stochastic Approximation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 28 May 2024.

## Builds on (most cited first, 18 of 18)

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2110.14427/) (2021)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/1912.10583/) (2019)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [Stability of Stochastic Approximations with `Controlled Markov' Noise and Temporal Difference Learning](https://mlsanity.com/paper/1504.06043/) (2015)
- [Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2405.14285/) (2024)
- [The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning](https://mlsanity.com/paper/2309.02944/) (2023)
- [The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize](https://mlsanity.com/paper/2405.16732/) (2024)
- [Markovian Foundations for Quasi-Stochastic Approximation with Applications to Extremum Seeking Control](https://mlsanity.com/paper/2207.06371/) (2022)

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

- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024)
- [Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approach](https://mlsanity.com/paper/2511.03618/) (2025)
- [Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2502.09884/) (2025)
- [Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way](https://mlsanity.com/paper/2410.13067/) (2024)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation](https://mlsanity.com/paper/2508.05570/) (2025)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling](https://mlsanity.com/paper/2608.10896/) (2026)
- [Convergence, Sticking and Escape: Stochastic Dynamics Near Critical Points in SGD](https://mlsanity.com/paper/2505.18535/) (2025)

## Abstract (arXiv)

Many machine learning and optimization algorithms are built upon the framework of stochastic approximation (SA), for which the selection of step-size (or learning rate) αn is crucial for success. An essential condition for convergence is the assumption that sumn αn = ∞. Moreover, in all theory to date it is assumed that sumn αn2 < ∞ (the sequence is square summable). In this paper it is shown for the first time that this assumption is not required for convergence and finer results. The main results are restricted to the special case αn = α0 n-ρ with ρ ∈ (0,1). The theory allows for parameter dependent Markovian noise as found in many applications of interest to the machine learning and optimization research communities. Rates of convergence are obtained for the standard algorithm, and for estimates obtained via the averaging technique of Polyak and Ruppert. bullet Parameter estimates converge with probability one, and in Lp for any p≥ 1. Moreover, the rate of convergence of the the mean-squared error (MSE) is O(αn), which is improved to O(max αn2,1/n ) with averaging. Finer results are obtained for linear SA: bullet The covariance of the estimates is optimal in the sense of prior work of Polyak and Ruppert. bullet Conditions are identified under which the bias decays faster than O(1/n). When these conditions are violated, the bias at iteration n is approximately βθαn for a vector βθ identified in the paper. Results from numerical experiments illustrate that βθ may be large due to a combination of multiplicative noise and Markovian memory.