Inference for Online Algorithms without Variance Estimation

Music City Center 

Inference for online algorithms is a difficult problem because estimation of asymptotic variance can inflate the computational cost. Previous works have proposed online estimation of the covariance matrix as well as batching methods to construct confidence intervals. In this work, we propose the use of the recently developed HulC procedure for uncertainty quantification in the online setting. The highlights of this procedure include: no inflation in the computational cost; no estimation of the asymptotic variance; and asymptotically exact coverage.

We compare the performance of this procedure with those of previous works in the context of linear and logistic regression over a wide range of covariance settings and dimension-aspect ratios. Our main finding is that we get comparable or better coverage properties compared to the methods that estimate the asymptotic variance.

Stochastic gradient descent

asymptotic variance

high-dimensional inference

HulC

distributed learning

martingales 

Section on Statistical Learning and Data Science