Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT
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.
Code (0)
등록된 구현이 없습니다.
Tasks
parameter estimationvalidMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Exponential Concentration in Stochastic Approximation
We analyze the behavior of stochastic approximation algorithms where iterates, in expectation, progress towards an objective at each step. When progress is proportional to the step size of the algorithm, we prove exponen…
Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems
Motivated by the problem of online canonical correlation analysis, we propose the \emph{Stochastic Scaled-Gradient Descent} (SSGD) algorithm for minimizing the expectation of a stochastic function over a generic Riemanni…
Weighted Averaged Stochastic Gradient Descent: Asymptotic Normality and Optimality
Stochastic Gradient Descent (SGD) is one of the most popular algorithms in statistical and machine learning due to its computational and memory efficiency. Various averaging schemes have been proposed to accelerate the c…
validGaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent
In this paper, we establish non-asymptotic convergence rates in the central limit theorem for Polyak-Ruppert-averaged iterates of stochastic gradient descent (SGD). Our analysis builds on the result of the Gaussian appro…
Asymptotic Analysis of Conditioned Stochastic Gradient Descent
In this paper, we investigate a general class of stochastic gradient descent (SGD) algorithms, called Conditioned SGD, based on a preconditioning of the gradient direction. Using a discrete-time approach with martingale …
Second-order methods