A Framework for Statistical Inference via Randomized Algorithms

Zhi-Xiang Zhang, Sokbae Lee, Edgar DobribanarXiv 2023 · DOI · arXiv

TL;DR

Randomized algorithms like sketching and stochastic gradient descent (SGD) are essential for big data, but their outputs are non-deterministic—run them twice, and you’ll get two different answers. This paper provides a rigorous statistical framework to build confidence intervals around these "fuzzy" results, allowing researchers to know exactly how much they can trust a randomized estimate without sacrificing the speed that makes these algorithms useful.

What Problem Does This Paper Address?

As datasets grow to terabytes and beyond, traditional "exact" algorithms (like standard Least Squares) become computationally prohibitive. To cope, we use randomized shortcuts: sketching (compressing the data into a smaller "sketch") or stochastic optimization (taking random steps toward a solution).

The catch? These algorithms introduce a new layer of uncertainty. Unlike traditional statistics, where uncertainty comes from the data-generating process, here the uncertainty is "algorithmic." If a randomized algorithm tells you a regression coefficient is 5.2, is it actually 5.2, or could it be anywhere between 4 and 6? Until now, there hasn't been a general, computationally efficient way to perform statistical inference—calculating confidence intervals and p-values—for these general randomized methods.

Methods

The authors propose a framework that treats the output of a randomized algorithm as a random variable and seeks its limiting distribution (the pattern the results follow as the algorithm does more work). They introduce three primary methods to estimate this uncertainty:

  1. Sub-randomization: Inspired by classical subsampling, this involves running the algorithm once at a large scale (the "main" result) and several times at a much smaller scale. By seeing how the results fluctuate at the small scale, we can predict the error at the large scale.
  2. Multi-run Plug-in: This is for cases where we know the output follows a Normal distribution (a "bell curve"). We run the algorithm several times at the same scale and use the variance of those runs to "plug in" to a standard confidence interval formula.
  3. Multi-run Aggregation: This is a "power-user" version of the plug-in method. If the algorithm has very low bias, we can average the results of multiple runs to get a more accurate estimate and a tighter confidence interval simultaneously.

The paper proves that these methods work for a wide variety of problems, including Sketch-and-Solve Least Squares and Stochastic Heavy Ball optimization (a popular momentum-based variant of SGD).

Datasets

The authors validated their framework using both synthetic simulations and real-world datasets:

  • Synthetic Data: They generated large-scale matrices using i.i.d. Normal and multivariate t-distributions to test the methods under different "noise" conditions.
  • Human Genome Diversity Project (HGDP): A dataset of Single Nucleotide Polymorphisms (SNPs) used to see if the framework could handle the complex correlations found in genetic data.
  • IPUMS USA Wage Data: A massive dataset of hourly wages (approx. 480,000 samples and 417 predictors). This was used to demonstrate the framework's performance on high-dimensional, "messy" empirical data.

Key Insights and Ideas

  • The "Data as Deterministic" Shift: Traditionally, statisticians view the data as random and the algorithm as fixed. This paper flips that: it treats the data as fixed (deterministic) and the algorithm as the source of randomness. This allows for inference even when we don't know the underlying distribution of the data.
  • Inference is "Almost Free": One of the biggest "aha" moments is that the communication and computation costs of these inference methods are often negligible. For example, the authors show that adding uncertainty quantification to a sketch only increases the data-loading cost by about 8-10%.
  • Parallelism is Key: Because the multi-run methods involve independent executions of the algorithm, they are "embarrassingly parallel." You can calculate your confidence interval in the same amount of time it takes to run the algorithm once, provided you have enough CPU cores.

Key Results

  • Speed vs. Accuracy: In a large-scale experiment with 1 million samples, the authors' "pivotal" inference method was 54% faster than a full OLS solution while maintaining a 90% coverage rate (meaning the true value fell within the calculated interval 90% of the time).
  • Memory Efficiency: The framework allowed for sub-randomization on a 130GB dataset using only 16GB of RAM, proving that these methods are viable for researchers without access to supercomputing clusters.
  • Robustness: The methods remained accurate even when the dimensionality of the data ($p$) grew along with the sample size ($n$), a scenario where many traditional statistical tools break down.

Limitations and Future Work

While the framework is broad, it relies on the algorithm having a stable "limiting distribution." If an algorithm is highly unstable or hasn't "settled down" yet, the confidence intervals might be inaccurate.

The authors suggest that future work could extend these tools to even more complex randomized techniques, such as Subsampled Randomized Hadamard Transforms or algorithms involving dependent data (like those used in reinforcement learning). They also note that while they focused on linear models, the framework could theoretically be adapted for non-linear "black-box" models in the future.

Summary updated

Abstract

Randomized algorithms, such as randomized sketching or stochastic optimization, are a promising approach to ease the computational burden in analyzing large datasets. However, randomized algorithms also produce non-deterministic outputs, leading to the problem of evaluating their accuracy. In this paper, we develop a statistical inference framework for quantifying the uncertainty of the outputs of randomized algorithms. Our key conclusion is that one can perform statistical inference for the target of a sequence of randomized algorithms as long as in the limit, their outputs fluctuate around the target according to any (possibly unknown) probability distribution. In this setting, we develop appropriate statistical inference methods -- sub-randomization, multi-run plug-in and multi-run aggregation -- by estimating the unknown parameters of the limiting distribution either using multiple runs of the randomized algorithm, or by tailored estimates. As illustrations, we develop methods for statistical inference when using stochastic optimization (such as Polyak-Ruppert averaging in stochastic gradient descent and stochastic optimization with momentum). We also illustrate our methods in inference for least squares parameters via randomized sketching, by characterizing the limiting distributions of sketching estimates in a possibly growing dimensional case. We further characterize the computation and communication cost of our methods, showing that in certain cases, they add negligible overhead. The results are supported via a broad range of simulations.
BibTeX
@misc{zhang2023framework,
  author = {Zhi-Xiang Zhang and Sokbae Lee and Edgar Dobriban},
  title = {{A Framework for Statistical Inference via Randomized Algorithms}},
  year = {2023},
  eprint = {2307.11255},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.11255},
}
Figure