# The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 28 references that are in the map.
- First posted on arXiv 6 Sep 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [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)
- [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, 7 of 7)

- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [Revisiting Step-Size Assumptions in Stochastic Approximation](https://mlsanity.com/paper/2405.17834/) (2024)
- [Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2405.14285/) (2024)
- [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)
- [Markovian Foundations for Quasi-Stochastic Approximation in Two Timescales: Extended Version](https://mlsanity.com/paper/2409.07842/) (2024)

## Abstract (arXiv)

Theory and application of stochastic approximation (SA) have become increasingly relevant due in part to applications in optimization and reinforcement learning. This paper takes a new look at SA with constant step-size α>0, defined by the recursion, θn+1 = θn+ α f(θn,Phin+1) in which θn∈ℝd and Phin is a Markov chain. The goal is to approximately solve root finding problem barf(θ^*)=0, where barf(θ)=mathbbE[f(θ,Phi)] and Phi has the steady-state distribution of Phin. The following conclusions are obtained under an ergodicity assumption on the Markov chain, compatible assumptions on f, and for α>0 sufficiently small: 1. The pair process (θn,Phin) is geometrically ergodic in a topological sense. 2. For every 1≤ p≤ 4, there is a constant bp such that limsupn→∞mathbbE[|θn-θ^*|p]≤ bp αp/2 for each initial condition. 3. The Polyak-Ruppert-style averaged estimates θPRn=n-1sumk=1nθk converge to a limit θPR_∞ almost surely and in mean square, which satisfies θPR_∞=θ^*+α barUpsilon^*+O(α2) for an identified non-random barUpsilon^*∈ℝd. Moreover, the covariance is approximately optimal: The limiting covariance matrix of θ^text PRn is approximately minimal in a matricial sense. The two main take-aways for practitioners are application-dependent. It is argued that, in applications to optimization, constant gain algorithms may be preferable even when the objective has multiple local minima; while a vanishing gain algorithm is preferable in applications to reinforcement learning due to the presence of bias.