2021/11/11 by Zaiwei Chen, Chen, Zaiwei, Shancong Mou +3
Computer Science · Mathematics · #Stochastic Gradient Optimization Techniques #Random Matrices and Applications #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2111.06328
Stochastic approximation (SA) and stochastic gradient descent (SGD)\nalgorithms are work-horses for modern machine learning algorithms. Their\nconstant stepsize variants are preferred in practice due to fast convergence\nbehavior. However, constant step stochastic iterative algorithms do not\nconverge asymptotically to the optimal solution, but instead have a stationary\ndistribution, which in general cannot be analytically characterized. In this\nwork, we study the asymptotic behavior of the appropriately scaled stationary\ndistribution, in the limit when the constant stepsize goes to zero.\nSpecifically, we consider the following three settings: (1) SGD algorithms with\nsmooth and strongly convex objective, (2) linear SA algorithms involving a\nHurwitz matrix, and (3) nonlinear SA algorithms involving a contractive\noperator. When the iterate is scaled by 1/\√(\α), where \α is\nthe constant stepsize, we show that the limiting scaled stationary distribution\nis a solution of an integral equation. Under a uniqueness assumption (which can\nbe removed in certain settings) on this equation, we further characterize the\nlimiting distribution as a Gaussian distribution whose covariance matrix is the\nunique solution of a suitable Lyapunov equation. For SA algorithms beyond these\ncases, our numerical experiments suggest that unlike central limit theorem type\nresults: (1) the scaling factor need not be 1/\√(\α), and (2) the\nlimiting distribution need not be Gaussian. Based on the numerical study, we\ncome up with a formula to determine the right scaling factor, and make\ninsightful connection to the Euler-Maruyama discretization scheme for\napproximating stochastic differential equations.\n