Statistical Inference for Online Algorithms
This work addresses the computational challenges of statistical inference for online algorithms, which is crucial for applications where data cannot be accessed repeatedly, offering a practical solution for researchers and practitioners in machine learning and statistics.
The paper tackles the problem of constructing confidence intervals and hypothesis tests for online algorithms without needing to estimate asymptotic variance, proposing a computationally efficient and asymptotically valid method. It demonstrates this approach using stochastic gradient descent with Polyak averaging, achieving rate-optimal performance.
Construction of confidence intervals and hypothesis tests for functionals based on asymptotically normal estimators is a classical topic in statistical inference. The simplest and in many cases optimal inference procedure is the Wald interval or the likelihood ratio test, both of which require an estimator and an estimate of the asymptotic variance of the estimator. Estimators obtained from online/sequential algorithms forces one to consider the computational aspects of the inference problem, i.e., one cannot access all of the data as many times as needed. Several works on this topic explored the online estimation of asymptotic variance. In this article, we propose computationally efficient, rate-optimal, and asymptotically valid confidence regions based on the output of online algorithms {\em without} estimating the asymptotic variance. As a special case, this implies inference from any algorithm that yields an asymptotically normal estimator. We focus our efforts on stochastic gradient descent with Polyak averaging to understand the practical performance of the proposed method.