High-Order Error Bounds for Markovian LSA with Richardson–Romberg Extrapolation

I. Levin; A. Naumov; S. Samsonov

doi:10.1609/aaai.v40i43.40994

Publications

?

High-Order Error Bounds for Markovian LSA with Richardson–Romberg Extrapolation

P. 36696–36704.

Levin I., Naumov A., Samsonov S.

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 the step size 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. We validate applicability of our findings for the temporal difference algorithm in reinforcement learning.

Keywords: Richardson-Romberg extrapolation linear stochastic approximation

In book

Proceedings of the AAAI Conference on Artificial Intelligence. AAAI-26: AAAI Technical Track on Planning, Routing, and Scheduling; AAAI Technical Track on Reasoning under Uncertainty; AAAI Technical Track on Search and Optimization. Main Track, volume 40 no. 43

American Association for Artificial Intelligence (AAAI) Press, 2026.

Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

Levin I., Shuklin M., Moulines E. et al., , in: Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence (UAI), PMLR Volume 337, 17-21 August 2026, KIT, Amsterdam, the NetherlandsVol. 337.: Proceedings of Machine Learning Research , 2026. Ch. 134 P. 3487–3545.

In this paper, we establish Berry-Esseen-type bounds for federated linear stochastic approximation (LSA). Our results provide the first federated {Gaussian} approximations for LSA that explicitly capture communication-computation trade-offs and heterogeneity-aware error terms, quantifying the effects of local step size, number of local updates, and heterogeneity on convergence rates. We present results for both (i) constant ...

Added: September 4, 2026

Statistical inference for Linear Stochastic Approximation with Markovian Noise

Samsonov S., Sheshukova M., Moulines E. et al., , in: 39th Conference on Neural Information Processing Systems (NeurIPS 2025).: NeurIPS, 2025. P. 174565–174626.

In this paper we derive non-asymptotic Berry-Esseen bounds for Polyak-Ruppert averaged iterates of the Linear Stochastic Approximation (LSA) algorithm driven by the Markovian noise. Our analysis yields O(n −1/4 ) convergence rates to the Gaussian limit in the Kolmogorov distance. We further establish the nonasymptotic validity of a multiplier block bootstrap procedure for constructing the ...

Added: January 26, 2026

Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation

Sheshukova M., Belomestny D., Durmus A. et al., , in: Proceedings of the 13th International Conference on Learning Representations (ICLR 2025).: ICLR, 2025.

Added: August 15, 2025

Refined Analysis of Constant Step Size Federated Averaging and Federated Richardson-Romberg Extrapolation

Paul M., Durmus A., Dieuleveut A. et al., , in: Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 3-5 May 2025, Splash Beach Resort in Mai Khao, Thailand, PMLR: vol. 258Vol. 258.: PMLR, 2025. Ch. 258 P. 5023–5031.

In this paper, we present a novel analysis of FedAvg with constant step size, relying on the Markov property of the underlying process. We demonstrate that the global iterates of the algorithm converge to a stationary distribution and analyze its resulting bias and variance relative to the problem’s solution. We provide a first-order bias expansion in ...

Added: May 18, 2025

SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning

Mangold P., Samsonov S., Labbi S. et al., , in: 38th Conference on Neural Information Processing Systems (NeurIPS 2024).: [б.и.], 2024. Ch. 37 P. 13927–13981.

In this paper, we analyze the sample and communication complexity of the federated linear stochastic approximation (FedLSA) algorithm. We explicitly quantify the effects of local training with agent heterogeneity. We show that the communication complexity of FedLSA scales polynomially with the inverse of the desired accuracy ϵ. To overcome this, we propose SCAFFLSA a new ...

Added: February 11, 2025

Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation

Sheshukova M., Belomestny D., Durmus A. et al., / Series arXiv "math". 2024.

We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with a constant step size. Previous works suggested to combine the Polyak-Ruppert averaging procedure with the Richardson-Romberg extrapolation technique to reduce the asymptotic bias of SGD at the expense of a mild increase of the variance. We ...

Added: October 13, 2024

Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability

Samsonov S., Tiapkin D., Naumov A. et al., , in: Proceedings of Machine Learning Research. Volume 247: The Thirty Seventh Annual Conference on Learning Theory, 30-3 July 2023, Edmonton, Canada.: PMLR, 2024. Ch. 247 P. 4511–4547.

Added: October 13, 2024

Finite-Time High-Probability Bounds for Polyak–Ruppert Averaged Iterates of Linear Stochastic Approximation

Durmus A., Moulines E., Naumov A. et al., Mathematics of Operations Research 2025 Vol. 50 No. 2 P. 935–964

This paper provides a finite-time analysis of linear stochastic approximation (LSA) algorithms with fixed step size, a core method in statistics and machine learning. LSA is used to compute approximate solutions of a $d$-dimensional linear system $\bar{\mathbf{A}} \theta = \bar{\mathbf{b}}$, for which $(\bar{\mathbf{A}}, \bar{\mathbf{b}})$ can only be estimated through (asymptotically) unbiased observations $\{(\mathbf{A}(Z_n),\mathbf{b}(Z_n))\}_{n \in \mathbb{N}}$. ...

Added: July 13, 2022

Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize

Durmus A., Moulines E., Naumov A. et al., , in: Advances in Neural Information Processing Systems 34 (NeurIPS 2021).: Curran Associates, Inc., 2021. P. 30063–30074.

This paper provides a non-asymptotic analysis of linear stochastic approximation (LSA) algorithms with fixed stepsize. This family of methods arises in many machine learning tasks and is used to obtain approximate solutions of a linear system $\bar{A}\theta = \bar{b}$ for which $\bar{A}$ and $\bar{b}$ can only be accessed through random estimates $\{({\bf A}_n, {\bf b}_n): ...

Added: February 17, 2022

On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning

Durmus A., Moulines E., Naumov A. et al., , in: Proceedings of Machine Learning ResearchVol. 134: Conference on Learning Theory.: PMLR, 2021. P. 1711–1752.

Added: August 6, 2021

A multi-step Richardson-Romberg extrapolation method for stochastic approximation

L.Huang, Frikha N., Stochastic Processes and their Applications 2015 No. 125 P. 4066–4101

We obtain an expansion of the implicit weak discretization error for the target of stochastic approximation algorithms introduced and studied in Frikha (2013). This allows us to extend and develop the Richardson–Romberg extrapolation method for Monte Carlo linear estimator (introduced in Talay and Tubaro (1990) and deeply studied in Pag`es (2007)) to the framework of stochastic optimization by ...

Added: October 14, 2015