Online Bootstrap for Averaged Stochastic Approximation with Momentum

We develop an online multiplier bootstrap for inference on parameters estimated by Polyak–Ruppert averaging in two classes of stochastic approximation algorithms: fixed momentum with fixed preconditioning, and dynamic preconditioning without momentum. The procedure updates weighted replicas alongside the original recursion, preserving one-pass computation and avoiding explicit estimation of the asymptotic covariance. Under mean and score regularity and rate conditions for both the original and weighted paths, we show that fixed momentum and fixed preconditioning do not affect the first-order influence function, and the resulting bootstrap remains valid for nonsmooth problems such as quantile regression. For dynamic preconditioning, we establish conditions under which the evolving preconditioner is asymptotically negligible, allowing bootstrap replicas to either reuse the original preconditioner sequence or maintain their own curvature states. This flexibility makes it possible to trade computational cost against how closely the replicas reproduce the original algorithm, without changing first-order inference. The framework supports valid inference with a fixed number of replicas as well as empirical bootstrap quantiles when more replicas are available. We also show that multiple evaluations generated from the same observation should share a common multiplier to preserve the correct covariance structure. Simulations and an application to the UCI Adult data illustrate the finite-sample performance and practical implementation of the proposed approach.