Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation

Seo Taek Kong; R. Srikant

cs.LGFeb 2, 2026

Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation

Authors: Seo Taek Kong, R. Srikant

Organizations: University of Illinois Urbana-Champaign

Abstract

Stochastic approximation methods such as stochastic gradient descent and temporal-difference learning return either the last iterate or the Polyak--Ruppert average. We establish finite-sample Wasserstein- $p$ Gaussian approximation bounds for both outputs under a common framework combining moment bounds for the normalized iterates with quantitative Gaussian approximation of the appropriately weighted driving noise. These bounds yield convergence of admissible moments and high probability bounds with Gaussian leading terms: heavier dependence on the confidence level is confined to a correction that vanishes with the sample size. We verify the framework's conditions for nonlinear stochastic approximation with independent or Markovian observations and linear stochastic approximation with Markovian observations, with applications to stochastic gradient descent and temporal-difference learning.

Figures & tables

Setting	Last iterate $\lVert\bm{y}_{n}\rVert$	PR average $\lVert\bar{\bm{y}}_{n}\rVert$
NM ( Corollary 1 )	$\mathcal{G}_{\mathbf{\Sigma}}\left(\delta-o(1)\right)+\mathcal{O}\left(\frac{1}{n^{1/4}}\right)$	$\mathcal{G}_{\bar{\mathbf{\Sigma}}}\left(\delta-o(1)\right)+\mathcal{O}\left(\frac{1}{n^{1/8}}\right)$
ID ( Corollary 2 )	$\mathcal{G}_{\mathbf{\Sigma}}\left(\delta-o(1)\right)+o(1)$	$\mathcal{G}_{\bar{\mathbf{\Sigma}}}\left(\delta-o(1)\right)+o(1)$
LM ( Corollary 3 )	$\begin{gathered}\left(1+o(1)\right)\mathcal{G}_{\mathbf{\Sigma}}\left(\frac{\delta}{2}\right)+\mathcal{O}\left(\frac{\log\left(\frac{2}{\delta}\right)}{n^{1/6}}\right)\end{gathered}$	$\begin{gathered}\left(1+o(1)\right)\mathcal{G}_{\bar{\mathbf{\Sigma}}}\left(\frac{\delta}{2}\right)+\mathcal{O}\left(\frac{\log\left(\frac{2}{\delta}\right)}{n^{1/6}}\right)\end{gathered}$

Table 1: Finite-sample high probability bounds for the three applications considered in Section 4 . NM, ID, and LM denote nonlinear Markov, nonlinear independent, and linear Markov stochastic approximation, respectively in Sections 4.1 , 4.2 and 4.3 . The

o(1)

describes a sequence that decays to zero as

n\to\infty

with all problem parameters fixed, and

\mathcal{O}

hides problem parameters independent of

n

and

\delta

. The exact rates are specified in Corollaries 1 , 2 and 3 .

Stochastic Approximation

Stochastic approximation studies iterative algorithms that solve optimization, root-finding, and fixed-point problems using noisy data.

See all 76 papers

Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, Gaussian Approximation, and Tail Bounds
Feb 15, 2026Zedong Wang, Yuyang Wang, Ijay Narang +3Stochastic Approximation Stochastic Gradient Descent
H. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA · Department of Mathematics, Brown University, Providence, RI 02912, USA · School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332, USA +2
Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation
Feb 14, 2025Seo Taek Kong, Sihan Zeng, Thinh T. Doan +1Stochastic Approximation Two-Timescale Stochastic Approximation
Coordinated Science Laboratory, Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801 USA · JP Morgan AI Research, Palo Alto, CA 94304 USA · Aerospace Engineering and Engineering Mechanics Department at University of Texas, Austin, Austin, TX 78712 USA
Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise
May 20, 2026Shubhada Agrawal, Siva Theja Maguluri, Martin ZubeldiaHeavy-Tailed Noise Stochastic Approximation
Indian Institute of Science · Georgia Institute of Technology · University of Minnesota

Feb 15, 2026J/K move · Enter open · S save

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

Zedong Wang, Yuyang Wang, Ijay Narang, Felix Wang+2

H. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA · Department of Mathematics, Brown University, Providence, RI 02912, USA · School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332, USA+2

Stochastic Approximation Stochastic Gradient Descent

Open paper AskPDF 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

X_k^{(α)} \approx X^{(α)} \approx x^\star+\sqrtαY

, where

X^{(α)}

is the steady state and

Y

is an appropriate Gaussian limit, by progressively taking the time

k\uparrow\infty

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

L^3

convergence of the steady state to the root

x^\star

, identifying the scale

\sqrtα

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

Stochastic Approximation

Explore similar work

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

Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation

Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise