Statistical inference for Linear Stochastic Approximation with Markovian Noise

Sergey Samsonov; Marina Sheshukova; Eric Moulines; Alexey Naumov

NeurIPS 2025poster0 citations

Statistical inference for Linear Stochastic Approximation with Markovian Noise

Sergey Samsonov, Marina Sheshukova, Eric Moulines, Alexey Naumov

Abstract

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.

Markovian LSAPolyak-Ruppert averagingBerry-Esseen type boundsBootstrap methodsAsymptotic variance estimation

BibTeX

@inproceedings{
samsonov2025statistical,
title={Statistical inference for Linear Stochastic Approximation with Markovian Noise},
author={Sergey Samsonov and Marina Sheshukova and Eric Moulines and Alexey Naumov},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=nWTQREGMLG}
}