Normal Approximation for Stochastic Gradient Descent via NonAsymptotic Rates of Martingale CLT
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:115137, 2019.
Abstract
We provide nonasymptotic convergence rates of the PolyakRuppert averaged stochastic gradient descent (SGD) to a normal random vector for a class of twicedifferentiable test functions. A crucial intermediate step is proving a nonasymptotic 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 nonasymptotic 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 nonasymptotic sense
Related Material


