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

2019/04/03 by Andreas Anastasiou, Krishnakumar Balasubramanian, Anastasiou, Andreas +3 · 5 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Probability (math.PR) #Random Matrices and Applications #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1904.02130

openalex publication_date 2019/04/03 · openalex created_date 2019/04/11 · openalex updated_date 2026/07/28

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.

Citations

• Stochastic Approximation: A Dynamical Systems Viewpoint
• A Multivariate CLT for Decomposable Random Vectors with Finite Second Moments
• Statistical Inference for Model Parameters in Stochastic Gradient Descent
• Uncertainty Quantification for Online Learning and Stochastic Approximation via Hierarchical Incremental Gradient Descent

Cited by

• Stopping Rules for Monte Carlo Methods of Martingale Difference Type
• Statistical Inference for Linear Functionals of Online Least-squares SGD when t \gtrsim d^1+δ
• Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation
• Central Limit Theorems for Asynchronous Averaged Q-Learning
• On the Rate of Gaussian Approximation for Linear Regression Problems
• Toward Optimal Statistical Inference in Noisy Linear Quadratic Reinforcement Learning over a Finite Horizon

Related

• Nonasymptotic CLT and Error Bounds for Two-Time-Scale Stochastic Approximation
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation
• Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning
• Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent