Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation
This provides statistical inference tools for practitioners using stochastic approximation in optimization and machine learning applications.
The paper tackles the problem of constructing time-uniform confidence intervals for parameters in stochastic approximation algorithms, developing asymptotic confidence sequences that maintain coverage guarantees uniformly across all time points after a sufficiently large starting time.
We study time-uniform statistical inference for parameters in stochastic approximation (SA), which encompasses a bunch of applications in optimization and machine learning. To that end, we analyze the almost-sure convergence rates of the averaged iterates to a scaled sum of Gaussians in both linear and nonlinear SA problems. We then construct three types of asymptotic confidence sequences that are valid uniformly across all times with coverage guarantees, in an asymptotic sense that the starting time is sufficiently large. These coverage guarantees remain valid if the unknown covariance matrix is replaced by its plug-in estimator, and we conduct experiments to validate our methodology.