# Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, Gaussian Approximation, and Tail Bounds

arXiv: https://arxiv.org/abs/2602.13960 · HTML: https://mlsanity.com/paper/2602.13960/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2026.

## Built on by (most cited first, 3 of 3)

- [Scaling Limits of Constant-Stepsize SGD at Flat Minima](https://mlsanity.com/paper/2607.16384/) (2026)
- [Moment-Accurate Gaussian Mixtures for Constant-Step Stochastic Approximation](https://mlsanity.com/paper/2610.05595/) (2026)
- [Gaussian Limits for SGD Without Stationary Moments](https://mlsanity.com/paper/2610.05599/) (2026)

## Abstract (arXiv)

Constant-stepsize stochastic approximation (SA) is widely used in learning for computational efficiency, yet the distribution of the iterates is typically intractable. Classical asymptotics results give Xk(α) ≈ X(α) ≈ x^star+√αY, where X(α) is the steady state and Y is an appropriate Gaussian limit, by progressively taking the time kuparrow∞ and stepsize αdownarrow0. Such limit results, however, do not quantify finite-time, finite-stepsize errors. We develop an explicit pre-limit characterization for SA with i.i.d. and Markovian noise. We establish existence and uniqueness of the stationary law, a geometric Wasserstein convergence to stationarity, and almost-sure and L3 convergence of the steady state to the root x^star, identifying the scale √α as first-order fluctuation. At this scale, we derive a higher-order quantitative Gaussian approximation with a Wasserstein error, using Stein's method and Poisson equation techniques. We further obtain non-uniform Berry--Esseen-type tail bounds, incorporating both steady-state approximation and finite-time convergence errors. We instantiate the theory for strongly convex smooth SGD, linear SA, and nonlinear contractive SA. Beyond strong convexity, for general convex SGD, we identify a Gibbs limiting law and prove a pre-limit Wasserstein approximation error under stability and Stein-equation hypothesis, which are validated numerically.