Statistical inference in two-stage observation models including algorithmic randomness

Randomized algorithms, such as random sampling, random projections, and stochastic optimization, are increasingly used to reduce the computational cost of modern statistical analysis. These algorithms introduce algorithmic randomness in addition to the sampling randomness in the data, and this extra source of variation complicates statistical inference. We develop a framework for valid inference in such two-stage observation models, where data are first generated from an underlying population process and are then analyzed through a randomized algorithm. Our method, called sub-randomization, runs the randomized algorithm multiple times at different computational scales and uses the auxiliary runs to approximate the conditional algorithmic error distribution. In important converging-scale settings, the procedure avoids estimating the limiting covariance matrix or other nuisance parameters in the limiting law. We illustrate the method in two settings where standard approaches can fail to achieve nominal coverage: inference from repeated observations with highly correlated noise, and confidence sets for the minimizers of stochastic optimization problems computed using momentum methods, with particular emphasis on the stochastic heavy ball algorithm.