Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD
Paper proves a sharp Gaussian approximation for the stationary law of constant-stepsize SGD.
The paper proves a sharp Gaussian approximation for the invariant distribution of constant-stepsize SGD driven by bounded noise from a uniformly ergodic Markov chain. For smooth strongly convex objectives with a Lipschitz Hessian and nondegenerate long-run noise covariance, the centered iterate scaled by the square root of the stepsize is O(sqrt(alpha))-close in 1-Wasserstein distance to a Gaussian. A four-state example matches that rate through a third-order mixed moment even when one-time noise is symmetric and lagged autocovariances vanish.
- Covers constant-stepsize SGD with Markovian additive noise.
- Error is O(sqrt(alpha)) in 1-Wasserstein distance.
- Assumes smooth strong convexity and a Lipschitz Hessian.
- A four-state chain shows the approximation rate is sharp.
Full article101 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.39144