High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation
stat.ML, cs.LG, math.OC, math.ST, stat.TH
Submitted: 2025-08-07
Updated: 2026-10-12
Comments: Revised the proofs of Proposition 7 and Corollary 6. The dependence on $α$ and $n$ remains unchanged, while the dependence on $τ_{\text{mix}}$ and $p$ is now less favorable
License: http://creativecommons.org/licenses/by/4.0/
The gist: In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise.
Terminology
Abstract
In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We focus on the version of the algorithm with constant step size α and propose a novel decomposition of the bias via a linearization technique. We analyze the structure of the bias and show that the leading-order term is linear in α and cannot be eliminated by PR averaging. To address this, we apply the Richardson-Romberg (RR) extrapolation procedure, which effectively cancels the leading bias term. We derive high-order moment bounds for the RR iterates and show that the leading error term aligns with the asymptotically optimal covariance matrix of the vanilla averaged LSA iterates.
Sources
- Rosenthal-type inequalities for linear statistics of Markov chains
- Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference
- The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning
- Revisiting Step-Size Assumptions in Stochastic Approximation
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation
- Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- Scalable Posterior Uncertainty for Flexible Density-Based Clustering
- Efficient quadratic entropy with distance sketches
- Embedding-Bias in Conditional Independence Testing