Statistical inference for Linear Stochastic Approximation with Markovian Noise
This work provides the first non-asymptotic guarantees for bootstrap-based confidence intervals in stochastic approximation with Markov noise, addressing inference challenges for researchers in optimization and statistics.
The paper tackles the problem of statistical inference for Linear Stochastic Approximation with Markovian noise by deriving non-asymptotic Berry-Esseen bounds and establishing the validity of a bootstrap procedure for confidence intervals, achieving convergence rates of O(n^{-1/4}) to the Gaussian limit and recovering O(n^{-1/8}) rates for variance estimation.
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 $\mathcal{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.