Stochastic Gradient Descent: A Nonlinear Time Series Perspective

Jiaqi Li; Zhipeng Lou; Stefan Richter; Wei Biao Wu

stat.MLOct 14, 2026

Stochastic Gradient Descent: A Nonlinear Time Series Perspective

Authors: Jiaqi Li, Zhipeng Lou, Stefan Richter, Wei Biao Wu

Organizations: Department of Statistics, Rice University, USA · Department of Mathematics, University of California, San Diego, USA · Institute of Applied Mathematics, Heidelberg University, Germany · Department of Statistics, University of Chicago, USA

Abstract

This paper investigates the statistical behavior of Stochastic Gradient Descent (SGD) with constant step size under the framework of iterated random functions. Compared to previous studies establishing the convergence of SGD in probability measure, e.g., Wasserstein distance, our approach directly provides the convergence in Euclidean distance by showing the Geometric Moment Contraction (GMC) of SGD. This new convergence can address the non-stationarity of SGD due to fixed initial points and can provide a more refined asymptotic analysis of SGD. Specifically, we prove quenched central limit theorem, invariance principle and $α$ -stable convergence for averaged SGD (ASGD) regardless of initialization. Furthermore, we provide a novel perspective to understand the impact of step sizes in SGD by studying its derivative with respect to the step size. The existence of stationary solutions for the derivative processes is shown, enabling the use of interpolation to recover the full-trajectory of SGD. Subsequently, we utilize multiple step sizes and show an enhanced Richardson-Romberg extrapolation with improved bias representation, which brings ASGD estimates closer to the global optimum. Finally, we propose a new online inference method and a bias-reduced variant for the extrapolated ASGD. Empirical confidence intervals are constructed and the coverage probabilities approach the nominal level as $n$ grows.

Figures & tables

Panel of Figure 1 — Figure 1: A simulation example illustrating GMC of SGD from initial values over multiple orders of magnitude. The optimum is $\theta^{\ast}=1$ , the constant step size is $\gamma=0.02$ , and we report $\mathbb{E}|\theta_{k}^{(\theta_{0})}-\theta_{k}^{(\theta^{\ast})}|^{2}$ on a logarithmic scale. The initializations vary from $\pm 10$ to $\pm 10^{5}$ for linear regression and from $\pm 3$ to $\pm 10^{2}$ for logistic regression.

Panel of Figure 2 — Figure 2: Spline interpolation on the last iterate of SGD, denoted by $\theta_{n}(\gamma)=(\theta_{n}^{(1)}(\gamma),\theta_{n}^{(2)}(\gamma))^{\top}$ , for the logistic regression ( $d=2$ ) with 6 internal knots shown as crosses. Fitted line by interpolation is shown in blue and the line of SGD estimates is shown in red.

Panel of Figure 3 — Figure 3: Recursively estimated long-run variance averaged over 500 independent runs (Linear regression $\gamma=0.025$ ). (Left) Bias of the two estimators. (Right) Empirical coverage probability of 95% confidence interval. The black dashed line indicates the nominal probability = 0.95.

Linear regression
step size	$n=5000$	$n=10^{4}$	$n=5\times 10^{4}$	$n=10^{5}$
$0.0125$	0.194 (0.0177)	0.332 (0.0211)	0.796 (0.0180)	0.904 (0.0132)
$0.0125$	0.198 (0.0178)	0.364 (0.0215)	0.854 (0.0158)	0.948 (0.0099)
$0.025$	0.278 (0.0200)	0.402 (0.0219)	0.844 (0.0162)	0.912 (0.0127)
$0.025$	0.286 (0.0202)	0.408 (0.0220)	0.854 (0.0158)	0.954 (0.0094)
$0.05$	0.266 (0.0198)	0.380 (0.0217)	0.810 (0.0175)	0.910 (0.0128)

Table 1: Empirical coverage probability of 95% confidence interval for linear regression and logistic regression over 500 independent runs. For each step size, the first row represents the estimator without bias reduction, and the second row represents the estimator with bias reduction. The standard error is reported in the brackets.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Order	$\mu_{\bm{b}}$	Types	Index	Number of Parameters
$\|\bm{b}\|=1$	$\mu_{i}$ , $1\leq i\leq d$	$\mathbb{E}[\theta_{1}]$	$\mathcal{A}_{1}$	$d$
$\|\bm{b}\|=2$	$\mu_{ij}$ , $1\leq i,j\leq d$	$\mathbb{E}[\theta_{1}\theta_{2}],\,\mathbb{E}[\theta_{1}^{2}]$	$\mathcal{A}_{2}$	${d\choose 2}+d$
$\|\bm{b}\|=3$	$\mu_{ijk}$ , $1\leq i,j,k\leq d$	$\mathbb{E}[\theta_{1}\theta_{2}\theta_{3}],\,\mathbb{E}[\theta_{1}^{2}\theta_{2}],\,\mathbb{E}[\theta_{1}^{3}]$	$\mathcal{A}_{3}$	${d\choose 3}+2{d\choose 2}+d$
$\|\bm{b}\|=4$	$\mu_{ijkl}$ , $1\leq i,j,k,l\leq d$	$\mathbb{E}[\theta_{1}\theta_{2}\theta_{3}\theta_{4}],\,\mathbb{E}[\theta_{1}^{2}\theta_{2}\theta_{3}],$	$\mathcal{A}_{4}$	${d\choose 4}+3{d\choose 3}+3{d\choose 2}+d$
		$\mathbb{E}[\theta_{1}^{3}\theta_{2}],\,\mathbb{E}[\theta_{1}^{2}\theta_{2}^{2}],\,\mathbb{E}[\theta_{1}^{4}]$

Appendix

Table 2: In total

\widetilde{d}=|\mathcal{A}_{1}|+|\mathcal{A}_{2}|+|\mathcal{A}_{3}|+|\mathcal{A}_{4}|

unknown parameters to solve, where

|\bm{b}|=\sum_{i=1}^{d}b_{i}

step size	estimator	$n=100$	$n=1000$	$n=5000$	$n=10^{4}$	$n=10^{5}$	$n=10^{6}$
$\gamma=0.025$	$\bar{\theta}_{n}(\gamma)$	1.942e-01	1.782e-02	4.520e-03	1.923e-03	1.823e-04	9.154e-05
	$\widehat{\theta}_{n}^{(2)}(\gamma)$	1.375e-01	1.462e-02	2.915e-03	1.355e-03	6.670e-05	8.489e-02
	$\widehat{\theta}_{n}^{(3)}(\gamma)$	8.638e-02	8.363e-03	2.823e-03	9.776e-04	2.470e-05	1.725e-02
$\gamma=0.05$	$\bar{\theta}_{n}(\gamma)$	1.145e-01	1.911e-02	5.352e-03	2.632e-03	5.348e-04	1.327e-04
	$\widehat{\theta}_{n}^{(2)}(\gamma)$	8.051e-02	7.328e-03	3.207e-03	1.066e-03	3.083e-04	8.604e-05
	$\widehat{\theta}_{n}^{(3)}(\gamma)$	5.274e-02	4.713e-03	2.490e-03	8.798e-04	1.410e-04	3.584e-02

Appendix

Table 3: Logistic regression. Absolute value of the average bias over 100 independent runs, where the target is penalized population minimizer.

Figure 4: Difference between the estimators with and without bias correction, i.e., $\widehat{\sigma}-\widetilde{\sigma}$ . The accuracy of the bias-reduced estimator outperforms the non-debiased one regardless of different step sizes.

Panel of Figure 5 — Figure 5: Recursive estimation of the long-run variance without bias reduction. The red line is the oracle value with $n=0.1$ billion.

Panel of Figure 6 — Figure 6: Recursive estimation of the long-run variance with bias reduction. The red line is the oracle value with $n=0.1$ billion.

Panel of Figure 7 — Figure 7: Recursive estimation of the long-run variance without bias reduction. The red line is the oracle value with $n=0.1$ billion.

Panel of Figure 8 — Figure 8: Recursive estimation of the long-run variance with bias reduction. The red line is the oracle value with $n=0.1$ billion.

Richardson Extrapolation

See all 8 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
Statistical Inference for Stochastic Gradient Descent Beyond Finite Variance
May 25, 2026Jose Blanchet, Peter Glynn, Wenhao YangStochastic Optimization Confidence Region Estimation
Management Science and Engineering, Stanford University
A Nonlinear Time-Series Theory for Constant-step SGD with Momentum
Oct 12, 2026Younghun Lee, Jake Zummo, Wei Biao WuStochastic Gradient Descent Stochastic Optimization Convergence
Department of Statistics, University of Chicago

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

Richardson Extrapolation

Explore similar work

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

Statistical Inference for Stochastic Gradient Descent Beyond Finite Variance

A Nonlinear Time-Series Theory for Constant-step SGD with Momentum