# Statistical inference in two-stage observation models including algorithmic randomness

arXiv: https://arxiv.org/abs/2307.11255 · HTML: https://mlsanity.com/paper/2307.11255/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2023.

## Built on by (most cited first, 1 of 1)

- [Inference in Randomized Least Squares and PCA via Normality of Quadratic Forms](https://mlsanity.com/paper/2404.00912/) (2024)

## Abstract (arXiv)

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.