Statistical Inference for Online Algorithms

This paper proposes HulC, a statistically sound and computationally efficient method for constructing confidence regions from the output of online algorithms, such as Stochastic Gradient Descent (SGD). Unlike traditional methods like the Wald interval, which require multiple passes over the data and can be computationally expensive, HulC provides rate-optimal and asymptotically valid confidence intervals without needing to estimate the asymptotic variance. The paper presents theoretical analysis showing HulC's validity under mild conditions and compares its performance against existing inference methods, including a plug-in ASGD method and a t-statistic approach, through simulations on linear and logistic regression tasks, highlighting the sensitivity of ASGD to step-size parameters and HulC's robustness.