no. 14 · Friday 13 November 2026
Sharp Gaussian approximation for Polyak–Ruppert averaged linear stochastic approximation
Abstract
We study how quickly the normalized Polyak–Ruppert average approaches its Gaussian limit in linear stochastic approximation with bounded i.i.d.\ coefficients. For step sizes decaying as $k^{-γ}$, with $1/2\leγ<1$, we prove an upper bound of order $n^{γ-1}$ on the approximation error over convex sets in fixed dimension. A matching lower bound holds for every fixed model. The fastest rate in this range is $n^{-1/2}$, attained at $γ=1/2$. We also obtain an $O(n^{-1/2})$ bound on the error of the recursive multiplier bootstrap procedure.
- comments
- 26 pages
- fields
- Probability, Statistics Theory