# Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 70 references that are in the map.
- First posted on arXiv 10 Feb 2025.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)
- [High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise](https://mlsanity.com/paper/2006.05610/) (2020)
- [Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT](https://mlsanity.com/paper/1904.02130/) (2019)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [Statistical Inference for Online Decision Making via Stochastic Gradient Descent](https://mlsanity.com/paper/2010.07341/) (2020)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [Statistical Inference for Policy Evaluation with Temporal Difference Learning](https://mlsanity.com/paper/2410.16106/) (2024)
- [Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimator](https://mlsanity.com/paper/2306.02205/) (2023)
- [High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization](https://mlsanity.com/paper/2401.09346/) (2024)
- [Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descent](https://mlsanity.com/paper/2212.14883/) (2022)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation](https://mlsanity.com/paper/2410.05106/) (2024)

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

- [Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation](https://mlsanity.com/paper/2510.12375/) (2025)
- [Statistical Inference for Online Algorithms](https://mlsanity.com/paper/2505.17300/) (2025)
- [On the Rate of Gaussian Approximation for Linear Regression Problems](https://mlsanity.com/paper/2509.14039/) (2025)
- [Sharp Gaussian approximations for Decentralized Federated Learning](https://mlsanity.com/paper/2505.08125/) (2025)
- [Gaussian Approximation for Asynchronous Q-learning](https://mlsanity.com/paper/2604.07323/) (2026)
- [When Does Dynamic Preconditioning Preserve the Polyak-Ruppert CLT? A Stabilization Threshold](https://mlsanity.com/paper/2604.23498/) (2026)
- [Statistical Inference on Gradient Flows](https://mlsanity.com/paper/2606.01257/) (2026)
- [Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction](https://mlsanity.com/paper/2604.21203/) (2026)
- [On Gaussian approximation for entropy-regularized Q-learning with function approximation](https://mlsanity.com/paper/2605.17678/) (2026)
- [Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation](https://mlsanity.com/paper/2605.19629/) (2026)

## Abstract (arXiv)

In this paper, we establish the non-asymptotic validity of the multiplier bootstrap procedure for constructing the confidence sets using the Stochastic Gradient Descent (SGD) algorithm. Under appropriate regularity conditions, our approach avoids the need to approximate the limiting covariance of Polyak-Ruppert SGD iterates, which allows us to derive approximation rates in convex distance of order up to 1/√n. Notably, this rate can be faster than the one that can be proven in the Polyak-Juditsky central limit theorem. To our knowledge, this provides the first fully non-asymptotic bound on the accuracy of bootstrap approximations in SGD algorithms. Our analysis builds on the Gaussian approximation results for nonlinear statistics of independent random variables.