mlsanityData to 14 Oct 2026

Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent

arXiv 2502.06719 ↗First posted 10 Feb 2025stat.ML cs.LG math.OCcited by 10

Not on the map. Why?

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.

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

22 of 70 references.

References · 22

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  3. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  4. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  5. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  6. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  7. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 88
  8. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  9. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
  10. 2020Online Covariance Matrix Estimation in Stochastic Gradient Descentcited by 37
  11. 2020High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noisecited by 31
  12. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
10 more
  1. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
  2. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  3. 2020Statistical Inference for Online Decision Making via Stochastic Gradient Descentcited by 17
  4. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  5. 2024Statistical Inference for Policy Evaluation with Temporal Difference Learningcited by 15
  6. 2023Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimatorcited by 13
  7. 2024High Confidence Level Inference is Almost Free using Parallel Stochastic Optimizationcited by 10
  8. 2022Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descentcited by 8
  9. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  10. 2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 6.

10 papers.

  1. 2025Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximationcited by 4
  2. 2025Statistical Inference for Online Algorithmscited by 2
  3. 2025On the Rate of Gaussian Approximation for Linear Regression Problemscited by 2
  4. 2025Sharp Gaussian approximations for Decentralized Federated Learningcited by 1
  5. 2026Gaussian Approximation for Asynchronous Q-learningcited by 1
  6. 2026When Does Dynamic Preconditioning Preserve the Polyak-Ruppert CLT? A Stabilization Thresholdcited by 1
  7. 2026Statistical Inference on Gradient Flowscited by 1
  8. 2026Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reductioncited by 0
  9. 2026On Gaussian approximation for entropy-regularized Q-learning with function approximationcited by 0
  10. 2026Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximationcited by 0