mlsanityData to 7 Oct 2026

Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise

arXiv 2405.14285 ↗First posted 23 May 2024stat.ML cs.LG math.OCcited by 9

Not on the map. Why?

Abstract (arXiv)

We study stochastic approximation algorithms with Markovian noise and constant step-size α. We develop a method based on infinitesimal generator comparisons to study the bias of the algorithm, which is the expected difference between θn -- the value at iteration n -- and θ^* -- the unique equilibrium of the corresponding ODE. We show that, under some smoothness conditions, this bias is of order O(α). Furthermore, we show that the time-averaged bias is equal to α V + O(α2), where V is a constant characterized by a Lyapunov equation, showing that mathbbE[barθn] ≈ θ^*+Vα + O(α2), where barθn=(1/n)sumk=1nθk is the Polyak-Ruppert average. We also show that barθn converges with high probability around θ^*+α V. We illustrate how to combine this with Richardson-Romberg extrapolation to derive an iterative scheme with a bias of order O(α2).

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 13 of its 40 references that are in the map. First posted on arXiv 23 May 2024.

Builds on

13 of 40 references.

References · 13

  1. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  2. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  3. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
  4. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  5. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 45
  6. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  7. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 28
  8. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  9. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  10. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  11. 2018Lyapunov Theory for Discrete Time Systemscited by 15
  12. 2023The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learningcited by 6
1 more
  1. 2023Hoeffding's Inequality for Markov Chains under Generalized Concentrability Conditioncited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 2; 2026: 4.

9 papers.

  1. 2024Revisiting Step-Size Assumptions in Stochastic Approximationcited by 10
  2. 2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6
  3. 2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5
  4. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  5. 2025Homogenization of Multi-agent Learning Dynamics in Finite-state Markov Gamescited by 0
  6. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 0
  7. 2026Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Samplingcited by 0
  8. 2026Beyond Client Averaging: A Client-Independent Second-Order Stationary-Bias Component in Stochastic SCAFFOLDcited by 0
  9. 2026Sharp Stationary Gaussian Approximation for Constant-Stepsize SGDcited by 0