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

arXiv:2602.13960v2 Announce Type: replace Abstract: 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 $X_k^{(\alpha)} \approx X^{(\alpha)} \approx x^\star+\sqrt{\alpha}Y$, where $X^{(\alpha)}$ is the steady state and $Y$ is an appropriate Gaussian limit, by progressively taking the time $k\uparrow\infty$ and stepsize $\alpha\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 $L^3$ convergence of the steady state to the root $x^\star$, identifying the scale $\sqrt{\alpha}$ 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.

Abstract: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 $X_k^{(\alpha)} \approx X^{(\alpha)} \approx x^\star+\sqrt{\alpha}Y$, where $X^{(\alpha)}$ is the steady state and $Y$ is an appropriate Gaussian limit, by progressively taking the time $k\uparrow\infty$ and stepsize $\alpha\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 $L^3$ convergence of the steady state to the root $x^\star$, identifying the scale $\sqrt{\alpha}$ 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.

Machine Learning (cs.LG); Probability (math.PR)

arXiv:2602.13960 [cs.LG]

(or arXiv:2602.13960v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2602.13960 Focus to learn more arXiv-issued DOI via DataCite

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.

analiza aiqbench

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

Subiecte conexe