Stochastic gradient descent convergence improves with new step size analysis
Stochastic Gradient Descent: A Nonlinear Time Series Perspective
Machine Learning
Summary
Stochastic Gradient Descent (SGD) is a method used to train computer models by iteratively improving them with small random steps. The authors found a new way to understand how SGD behaves over time that gives more precise results than before. They showed this method works well even if you start with any initial guess, and developed techniques to make the training process more reliable and closer to the best solution. This includes creating ways to estimate accuracy online and reduce errors from fixed step sizes in training.
What this means in practice
- •For machine learning engineers: Improve model training stability and accuracy by using refined step size adjustments and bias-reduced averaging methods for stochastic gradient descent.
- •For statistical software developers: Build tools that provide real-time confidence intervals and bias corrections for iterative algorithms like SGD on streaming data.
Authors
Jiaqi Li, Zhipeng Lou, Stefan Richter, Wei Biao Wu
Abstract
This paper investigates the statistical behavior of Stochastic Gradient Descent (SGD) with constant step size under the framework of iterated random functions. Compared to previous studies establishing the convergence of SGD in probability measure, e.g., Wasserstein distance, our approach directly provides the convergence in Euclidean distance by showing the Geometric Moment Contraction (GMC) of SGD. This new convergence can address the non-stationarity of SGD due to fixed initial points and can provide a more refined asymptotic analysis of SGD. Specifically, we prove quenched central limit theorem, invariance principle and $α$-stable convergence for averaged SGD (ASGD) regardless of initialization. Furthermore, we provide a novel perspective to understand the impact of step sizes in SGD by studying its derivative with respect to the step size. The existence of stationary solutions for the derivative processes is shown, enabling the use of interpolation to recover the full-trajectory of SGD. Subsequently, we utilize multiple step sizes and show an enhanced Richardson-Romberg extrapolation with improved bias representation, which brings ASGD estimates closer to the global optimum. Finally, we propose a new online inference method and a bias-reduced variant for the extrapolated ASGD. Empirical confidence intervals are constructed and the coverage probabilities approach the nominal level as $n$ grows.