Optimization Papers

Sharp Gaussian approximation for Polyak--Ruppert averaged linear stochastic approximation

Butyrin et al.

For step sizes \(k^{-\gamma}\) with \(1/2 \le \gamma < 1\), the averaged iterate of linear stochastic approximation is within \(O(n^{\gamma-1})\) of its Gaussian limit on convex sets, and the rate is sharp.

Filed under Optimization, Probability

Polyak-Ruppert averaging is the standard way to obtain asymptotically efficient estimates from stochastic approximation, and its central limit theorem is the basis for confidence intervals. The paper asks how fast the normalised average reaches that Gaussian limit when the coefficients are bounded and i.i.d.

With step sizes decaying as \(k^{-\gamma}\), \(1/2 \le \gamma < 1\), the authors prove an upper bound of order \(n^{\gamma-1}\) on the approximation error over convex sets in fixed dimension, and a matching lower bound for every fixed model. The best rate in the range, \(n^{-1/2}\), is reached at \(\gamma = 1/2\). They also bound the error of the recursive multiplier bootstrap by \(O(n^{-1/2})\), which gives a justified way to build confidence sets online.