Statistical inference for Linear Stochastic Approximation with Markovian Noise

Sergey Samsonov (National Research University Higher School of Economics) · Marina Sheshukova (Higher School of Economics) · Eric Moulines (Mohamed bin Zayed University of Artificial Intelligence) · Alexey Naumov (HSE University)

asymptotic varianceberry–esseen boundsbootstrap-based methodsconfidence intervalsconsistent inferenceconvergence ratesgaussian limitkolmogorov distancelinear stochastic approximationlogarithmic factorsmarkovian noisemultiplier block bootstrapnon-asymptotic analysisnon-asymptotic guaranteespolyak–ruppert averagingstochastic approximation

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 non-asymptotic validity of a multiplier block bootstrap procedure for constructing the confidence intervals, guaranteeing consistent inference under Markovian sampling. Our work provides the first non-asymptotic guarantees on the rate of convergence of bootstrap-based confidence intervals for stochastic approximation with Markov noise. Moreover, we recover the classical rate of order $\mathcal{O}(n^{-1/8})$ up to logarithmic factors for estimating the asymptotic variance of the iterates of the LSA algorithm.