# Cheap Bootstrap for Fast Uncertainty Quantification of Stochastic Gradient Descent

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 17 Oct 2023.

## Builds on (most cited first, 13 of 13)

- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT](https://mlsanity.com/paper/1904.02130/) (2019)
- [Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling](https://mlsanity.com/paper/2106.03156/) (2021)
- [Statistical inference using SGD](https://mlsanity.com/paper/1705.07477/) (2017)
- [HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation](https://mlsanity.com/paper/1802.04876/) (2018)
- [On Constructing Confidence Region for Model Parameters in Stochastic Gradient Descent via Batch Means](https://mlsanity.com/paper/1911.01483/) (2019)
- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (2021)
- [Estimating the Algorithmic Variance of Randomized Ensembles via the Bootstrap](https://mlsanity.com/paper/1907.08742/) (2019)
- [Measuring the Algorithmic Convergence of Randomized Ensembles: The Regression Setting](https://mlsanity.com/paper/1908.01251/) (2019)
- [A Cheap Bootstrap Method for Fast Inference](https://mlsanity.com/paper/2202.00090/) (2022)
- [Bootstrap in High Dimension with Low Computation](https://mlsanity.com/paper/2210.10974/) (2022)

## Abstract (arXiv)

Stochastic gradient descent (SGD) or stochastic approximation has been widely used in model training and stochastic optimization. While there is a huge literature on analyzing its convergence, inference on the obtained solutions from SGD has only been recently studied, yet it is important due to the growing need for uncertainty quantification. We investigate two computationally cheap resampling-based methods to construct confidence intervals for SGD solutions. One uses multiple, but few, SGDs in parallel via resampling with replacement from the data, and another operates this in an online fashion. Our methods can be regarded as enhancements of established bootstrap schemes to substantially reduce the computation effort in terms of resampling requirements, while bypassing the intricate mixing conditions in existing batching methods. We achieve these via a recent so-called cheap bootstrap idea and refinement of a Berry-Esseen-type bound for SGD.