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

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

## Key facts

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

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

- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling](https://mlsanity.com/paper/2106.03156/) (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)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization](https://mlsanity.com/paper/2401.09346/) (2024)
- [Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent](https://mlsanity.com/paper/2502.06719/) (2025)
- [Weighted Averaged Stochastic Gradient Descent: Asymptotic Normality and Optimality](https://mlsanity.com/paper/2307.06915/) (2023)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance](https://mlsanity.com/paper/2304.00707/) (2023)
- [Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2502.09884/) (2025)
- [Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data](https://mlsanity.com/paper/2405.19463/) (2024)
- [Online Covariance Estimation in Nonsmooth Stochastic Approximation](https://mlsanity.com/paper/2502.05305/) (2025)
- [Central Limit Theorems for Asynchronous Averaged Q-Learning](https://mlsanity.com/paper/2509.18964/) (2025)
- [Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation](https://mlsanity.com/paper/2510.12375/) (2025)
- [SGMM: Stochastic Approximation to Generalized Method of Moments](https://mlsanity.com/paper/2308.13564/) (2023)
- [Statistical Estimation and Inference via Local SGD in Federated Learning](https://mlsanity.com/paper/2109.01326/) (2021)
- [Generalization Bounds for Markov Algorithms through Entropy Flow Computations](https://mlsanity.com/paper/2502.07584/) (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)
- [Learning Curves for SGD on Structured Features](https://mlsanity.com/paper/2106.02713/) (2021)
- [Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression](https://mlsanity.com/paper/2302.09727/) (2023)
- [Sharp Gaussian approximations for Decentralized Federated Learning](https://mlsanity.com/paper/2505.08125/) (2025)
- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [Limit Theorems for Stochastic Gradient Descent in High-Dimensional Single-Layer Networks](https://mlsanity.com/paper/2511.02258/) (2025)
- [Gaussian Approximation in Wasserstein-p: Markovian Martingale Differences and Stochastic Approximation](https://mlsanity.com/paper/2609.09480/) (2026)
- [Cheap Bootstrap for Fast Uncertainty Quantification of Stochastic Gradient Descent](https://mlsanity.com/paper/2310.11065/) (2023)
- [Multiple Instance Learning for Uplift Modeling](https://mlsanity.com/paper/2312.09639/) (2023)
- [Large-scale Uncertainty Quantification for Latent Variable Models Using Subsampling Markov Chain Monte Carlo](https://mlsanity.com/paper/2606.00309/) (2026)

## 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.