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

Abstract

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.

References in corpus (4)

• Convergence rates of sub-sampled Newton methods
• Statistical Inference for Model Parameters in Stochastic Gradient Descent
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• Deterministic Inequalities for Smooth M-estimators

Cited by in corpus (5)

• Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling
• Multiple Instance Learning for Uplift Modeling
• Statistical Estimation and Inference via Local SGD in Federated Learning
• Learning Curves for SGD on Structured Features
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm