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.
Figures & tables
Figure 1: In subfigures (a), (b) and (c), we consider the step size α=n−β . Subfigure (a): error for RR iterations ( 48 ). Subfigure (b): error for PR iterations ( 2 ). Subfigure (c): error for RR, multiplied by a factor n2−β , which corresponds to the leading term of ( 59 ) after substituting α . Subfigure (d): MSE of Polyak-Ruppert and Richardson-Romberg iterations for different step sizes α .
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Variable
Description
Reference
Q
Solution of Lyapunov equation for Aˉ
Proposition 10
κQ
λmin−1(Q)λmax(Q)
Proposition 10
a
Real part of minimum eigenvalue of Aˉ
Proposition 10
Γm:n(α)
Product of random matrices with step size α
( 23 )
ε(Zn)
Noise in LSA procedure
( 9 )
θ~n(tr),θ~n(fl)
Transient and fluctuation terms of LSA error
( 25 )
Appendix
Table 1: Constants, definitions, notations
Figure 2: Comparison of remainder errors for Polyak-Ruppert averaged and Richardson-Romberg iterates in two regimes. In the first regime (a), the error attains its optimum for PR averaging, whereas for RR iterates it decays as predicted by Theorem 2 . Conversely, in the second regime (b), the optimum is achieved for RR iterates, which is also consistent with the theory.
Figure 3: Subfigure (a): the MSE remainder term for the Richardson-Romberg iterates is well approximated by rc−1 for some constant r>0 , matching the leading term (αn)−1n−1 in ( 59 ). Subfigure (b): rescaled by n4/3 MSE remainder trajectories for varying step sizes α . These plots cease decaying and stabilize, confirming the predicted order of the remainder term.