aiqbench analysis
This paper establishes a rigorous Gaussian approximation for the invariant distribution of constant-stepsize stochastic gradient descent when noise stems from an ergodic Markov chain, refining theoretical bounds on convergence behavior under non-i.i.d. conditions. By combining blockwise Gaussian comparison with long-run contraction techniques, the authors demonstrate that even with symmetric noise marginals and vanishing autocovariances, higher-order moments can produce significant corrections to the limiting distribution. These findings are critical for practitioners relying on SGD in environments with correlated data or complex noise structures, offering tighter error estimates for optimization algorithms.
Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD
arXiv:2609.39144v1 Announce Type: new 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{\alpha})$-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.
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{\alpha})$-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.
Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2609.39144 [cs.LG]
(or arXiv:2609.39144v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.39144 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 199 words
Related coverage
Steady-State Convergence of Stochastic Approximation
arXiv · Sep 15, 2026
Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, Gaussian Approximation, and Tail Bounds
arXiv · Sep 9, 2026
Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA
arXiv · Sep 15, 2026
Moment-Accurate Gaussian Mixtures for Constant-Step Stochastic Approximation
arXiv · Oct 6, 2026