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

Feb 15, 2026

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

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.

Zedong Wang, Yuyang Wang, Ijay Narang +3

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

Ask PDF

May 25, 2026

Statistical Inference for Stochastic Gradient Descent Beyond Finite Variance

Stochastic gradient descent (SGD) is a foundational algorithm for large-scale statistical learning and stochastic optimization. However, statistical inference based on SGD iterates remains challenging when stochastic gradients have infinite variance, as the relevant limiting distributions depend on unknown nuisance parameters. In this paper, we develop an efficient, model-agnostic methodology for constructing confidence regions from SGD trajectories that applies in both finite- and infinite-variance regimes. The procedure is based on a joint weak convergence result for the Polyak-Ruppert averaged estimator and an empirical second-moment normalizer constructed from stochastic gradients along the SGD trajectory. This joint limit yields a self-normalized statistic in which the leading tail-dependent scaling terms cancel. We then use a subsampling calibration scheme to estimate the relevant critical values, avoiding explicit estimation of tail indices, slowly varying functions, or stable-law parameters. The resulting confidence regions are straightforward to implement and are asymptotically valid under both the finite- and infinite-second-moment regimes. Simulation studies show reliable coverage in various settings, supporting the proposed method as a practical tool for uncertainty quantification in stochastic optimization.

Jose Blanchet, Peter Glynn, Wenhao Yang

Management Science and Engineering, Stanford University

Stochastic Optimization Confidence Region Estimation Uncertainty Quantification Stochastic Gradient Descent

Ask PDF

Oct 12, 2026

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

Constant-step stochastic gradient descent with momentum (SGDM) augments the parameter recursion with a momentum state that carries geometrically decaying memory of past stochastic gradients. We study this coupled recursion as a nonlinear time series and develop a framework for its stationary behavior and distributional limits. The joint parameter-momentum process forgets its initialization geometrically under a finite

p

th moment for

p > 1

, yielding a unique stationary causal solution. Under a second-moment condition, this contraction leads to an invariance principle and quenched Gaussian limit for averaged SGDM, while a small-learning-rate analysis gives a Gaussian limit for the last iterate. In a stochastic-curvature quadratic model, we further study how the rate of initialization forgetting relates to stationary variance and averaged fluctuations.

Younghun Lee, Jake Zummo, Wei Biao Wu

Department of Statistics, University of Chicago

Stochastic Gradient Descent Stochastic Optimization Convergence Stochastic Approximation

Ask PDF

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