A0702
Title: Asymptotic theory for constant step size stochastic gradient descent
Authors: Stefan Richter - HHU Duesseldorf (Germany) [presenting]
Wei Biao Wu - University of Chicago (United States)
Zhipeng Lou - University of Pittsburgh (United States)
Jiaqi Li - University of Chicago (United States)
Abstract: A novel approach is presented to understanding the behavior of stochastic gradient descent (SGD) with constant step size by interpreting its evolution as a Markov chain. Unlike previous studies that rely on the Wasserstein distance, this approach leverages the functional dependence measure, and the geometric-moment contraction (GMC) property is explored to capture the general asymptotic behavior 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 is established for the derivative SGD process 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.
