mlsanityData to 7 Oct 2026

Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT

arXiv 1904.02130 ↗First posted 3 Apr 2019math.ST math.OC math.PRcited by 30

Not on the map. Why?

Abstract (arXiv)

We provide non-asymptotic convergence rates of the Polyak-Ruppert averaged stochastic gradient descent (SGD) to a normal random vector for a class of twice-differentiable test functions. A crucial intermediate step is proving a non-asymptotic martingale central limit theorem (CLT), i.e., establishing the rates of convergence of a multivariate martingale difference sequence to a normal random vector, which might be of independent interest. We obtain the explicit rates for the multivariate martingale CLT using a combination of Stein's method and Lindeberg's argument, which is then used in conjunction with a non-asymptotic analysis of averaged SGD proposed in [PJ92]. Our results have potentially interesting consequences for computing confidence intervals for parameter estimation with SGD and constructing hypothesis tests with SGD that are valid in a non-asymptotic sense.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Apr 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 1; 2023: 7; 2024: 4; 2025: 11; 2026: 2.

30 papers.

Sort:

  1. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 69
  2. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 34
  3. 2021Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scalingcited by 28
  4. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  5. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  6. 2024High Confidence Level Inference is Almost Free using Parallel Stochastic Optimizationcited by 9
  7. 2025Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descentcited by 8
  8. 2023Weighted Averaged Stochastic Gradient Descent: Asymptotic Normality and Optimalitycited by 7
  9. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  10. 2021Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithmcited by 6
  11. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  12. 2023High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariancecited by 5
18 more
  1. 2024Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Datacited by 4
  2. 2025Online Covariance Estimation in Nonsmooth Stochastic Approximationcited by 4
  3. 2023SGMM: Stochastic Approximation to Generalized Method of Momentscited by 3
  4. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 3
  5. 2021Statistical Estimation and Inference via Local SGD in Federated Learningcited by 2
  6. 2025Generalization Bounds for Markov Algorithms through Entropy Flow Computationscited by 2
  7. 2025Statistical Inference for Online Algorithmscited by 2
  8. 2025Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximationcited by 2
  9. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  10. 2025Sharp Gaussian approximations for Decentralized Federated Learningcited by 1
  11. 2025On the Rate of Gaussian Approximation for Linear Regression Problemscited by 1
  12. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  13. 2025Limit Theorems for Stochastic Gradient Descent in High-Dimensional Single-Layer Networkscited by 1
  14. 2026Gaussian Approximation for Multivariate Martingale Sums from Uniformly Ergodic Markov Chainscited by 1
  15. 2021Learning Curves for SGD on Structured Featurescited by 0
  16. 2023Cheap Bootstrap for Fast Uncertainty Quantification of Stochastic Gradient Descentcited by 0
  17. 2023Multiple Instance Learning for Uplift Modelingcited by 0
  18. 2026Large-scale Uncertainty Quantification for Latent Variable Models Using Subsampling Markov Chain Monte Carlocited by 0