B1503
Title: Asymptotic theory for constant step size stochastic gradient descent
Authors: Stefan Richter - Heidelberg University (Germany) [presenting]
Wei Biao Wu - University of Chicago (United States)
Jiaqi Li - University of Chicago (United States)
Zhipeng Lou - University of Pittsburgh (United States)
Abstract: A novel approach to understanding the behaviour of stochastic gradient descent (SGD) with constant step size is presented by interpreting its evolution as a Markov chain. Unlike previous studies that rely on the Wasserstein distance, the approach leverages the functional dependence measure and explores the geometric-moment contraction (GMC) property to capture the general asymptotic behaviour of SGD in a more refined way. In particular, the approach allows SGD iterates to be non-stationary but asymptotically stationary over time, providing quenched versions of the central limit theorem and invariance principle valid for averaged SGD with any given starting point. A Richardson-Romberg extrapolation is subsequently defined with an improved bias representation to bring the estimates closer to the global optimum. The existence of a stationary solution for the derivative SGD process is established under mild conditions, enhancing the understanding of the entire SGD procedure. Lastly, an efficient online method is proposed for estimating the long-run variance of SGD solutions.
