Constant stepsize sgd iterates closely follow a specific gaussian pattern
Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD
Machine Learning
Summary
Stochastic gradient descent (SGD) is a method often used to find the best settings for a model by taking small steps. This paper shows that when these steps have a fixed size and the noise involved behaves well, the long-term behavior of the updates can be closely approximated by a bell-shaped curve (Gaussian). The authors prove a precise mathematical way to measure how close the updates are to this curve and demonstrate why this approximation is sharp. They also provide an example where this approximation is as accurate as possible, giving insight into the noise's role in the process.
What this means in practice
- •For machine learning engineers: Understand precise error behavior of constant-stepsize SGD under realistic noise to improve training stability analysis.
- •For algorithm designers: Rule out simpler noise models when designing SGD variants by understanding the impact of higher-order noise moments on convergence.
A theory result. No direct application yet.
Authors
Junghoon Seo
Abstract
We prove a sharp Gaussian approximation for the invariant law of constant-stepsize SGD with bounded additive noise generated by an exogenous uniformly ergodic Markov chain. For a smooth, strongly convex objective with a Lipschitz Hessian and nondegenerate long-run noise covariance, the centered iterate normalized by the square root of the stepsize is $O(\sqrtα)$-close in 1-Wasserstein distance to its limiting Gaussian. The proof combines blockwise Gaussian comparison with long-run contraction. A four-state example gives a matching lower bound although the one-time noise marginal is symmetric and every nonzero-lag autocovariance vanishes. In this example, an adjacent third-order mixed moment produces the leading correction.