Stochastic Gradient Descent: A Nonlinear Time Series Perspective

• Modeling SGD as an iterated random function and proving geometric moment contraction yields direct Lp-coupling in Euclidean norm between trajectories from different initial points.The paper establishes this contraction for a specified range of step sizes.Source: §1 · p. 3
• GMC supports all p-th moments for p > 1, ensures a unique stationary distribution, and enables asymptotic theory for the observed SGD process from arbitrary initial points.The framework addresses non-stationarity caused by fixed initialization.Source: §1 · p. 4
• Unlike diffusion approximations for small step sizes, this framework works directly with discrete-time constant-step SGD and yields Brownian approximation rates in probability.The authors present it as a route to approximation rates for weak convergence of SGD iterates.Source: §1 · p. 4
• For ASGD, the paper proposes online inference and establishes asymptotic stationarity and a quenched CLT for arbitrary initial points.The introduction also states that, under regularity conditions, averaged iterates converge at rate O_P(n^-1/2) to a point.Source: §1 · p. 5
• The paper establishes a quenched invariance principle for the ASGD process, with the weak convergence holding for every initial point.The limiting process is a standard d-dimensional Brownian motion.Source: §1 · p. 6
• The introduction gives a step-size range ensuring moment contraction and uses GMC to establish first- and second-order derivative processes with respect to the step size.The range is presented as guidance for practical step-size selection.Source: §1 · p. 6

Contributions

• Derivative processes for constant-step-size SGD have stationary solutions and moment properties, enabling interpolation to recover trajectories across a continuum of step sizes.The paper presents derivative processes as tools for measuring a non-stationary time series’ deviation from stationarity.Source: §1 · pp. 6–7
• An enhanced non-asymptotic bias expansion underlies an extrapolated ASGD estimator using three step sizes, with weights chosen to cancel the γΔ1 and γ^2Δ2 bias components.The stationary ASGD with constant step size γ is biased.Source: §1 · p. 7
• The proposed blocking-based online long-run covariance estimator has a better MSE rate under dependence, and empirical confidence intervals show desirable coverage probabilities.The confidence-interval coverage is reported in numerical experiments.Source: §1 · p. 7
• SGD is modeled as an iterated random function, with convergence in Euclidean norm established for an explicit range of step sizes.This provides a direct convergence result for the SGD process.Source: §1 · p. 7
• Quenched limiting distributions are established for averaged SGD with arbitrary initial points, alongside a debiased variant with optimal MSE among batch-means estimators.These results support an online inference method.Source: §1 · p. 8

GMC implications

• GMC directly bounds the coupled Euclidean distance between SGD trajectories from different initial values, with geometric decay that makes initialization forgotten exponentially fast.The stationary coupling also controls initialization in p-Wasserstein distance and supports limiting-distribution and concentration analyses.Source: §2 · pp. 9, 10, 13

Illustration

• In simulations of linear and penalized logistic regression, trajectories from varied initial values approach a reference trajectory at an exponential rate.Figure 1 reports squared trajectory differences for initializations spanning multiple orders of magnitude.Source: §2 · p. 10, Figure 1 · p. 10

Moment conditions

• The stochastic-gradient moment condition permits any p > 1, including fractional p, extending Lp convergence to cases with infinite variance.The paper identifies this range as an extension beyond prior assumptions requiring p ≥ 2 and integer p.Source: §2 · pp. 11, 13

Proof technique

• For 1 < p < 2, new Lp moment inequalities establish contraction without relying on unavailable second-moment arguments.These inequalities may also help analyze other online-learning recursions with heavy-tailed updates.Source: §2 · p. 12

Theorem 1

• For p > 1 and 0 < γ < γ(p), SGD has GMC and converges from every initialization to a unique stationary distribution with finite p-th moment.The result assumes strong convexity and stochastic Lipschitz continuity of the gradient.Source: §2 · pp. 12–13

2 Geometric Moment Contraction

• The paper’s conditions are less restrictive than almost-sure L-co-coercivity, as illustrated by a linear model and described as equivalent to a relaxed co-coercivity condition.Source: §2 · pp. 13–14
• In the stated linear-regression special case, 0 < γ < 2/ϖ; for γ ≥ 2/ϖ, the stationary distribution πγ has no finite second moment.The paper states that this p = 2 step-size range cannot generally be improved.Source: §2 · p. 14
• The direct bound on the SGD random-function difference avoids martingale decomposition, requiring a p-th moment rather than a 2p-th moment for GMC, which holds for all p > 1.This accommodates distributions with infinite variance; the paper also provides quenched α-stable convergence for ASGD with heavy-tailed noise in Appendix B.Source: §2 · p. 15
• GMC characterizes SGD’s dependence on its initial condition, which decays exponentially as the iteration number grows, and supports ASGD convergence results for arbitrary initial conditions.The paper identifies these results as a basis for refined ASGD limiting behavior, including quenched central limit theorems and statistical inference.Source: §2 · p. 15

3 Asymptotic Theory

• Under the conditions of Theorem 1, the p-th order moment convergence has bound O(n^(1/(p∧2)-1)), alongside an almost-sure convergence result.Source: §3.1 · p. 16

3.1 Quenched Central Limit Theorem

• Under the stated p = 2 conditions, the quenched central limit theorem for ASGD holds from any initial point.The paper addresses non-stationarity by approximating the arbitrarily initialized SGD sequence with a stationary process.Source: §3.1 · p. 16

3.2 Quenched Invariance Principles

• For p > 2, the quenched invariance principle gives an asymptotic distribution for the entire SGD path, not only final or averaged iterates.The result applies to arbitrary initial points and does not require γ → 0.Source: §3.2 · pp. 17–18

4 Derivative SGD Processes

• Step-size derivatives support interpolation across step sizes, avoiding separate SGD runs at every value and enabling reconstruction of a continuous spectrum of SGD orbits.The paper motivates this approach by noting that smaller step sizes slow convergence while larger ones may cause instability.Source: §4 · p. 18

4.1 Existence of the First Derivative Processes

• Under Theorem 1's conditions, a stationary first-derivative process with finite p-th moment exists, and derivatives from arbitrary initialization converge to it.The process is defined through a stationary linear stochastic recursion rather than by differentiating the two-sided stationary SGD recursion directly.Source: §4.1 · pp. 19–20

4.2 Existence of the Second Derivative Processes

• For p > 2 and finite p-th moment of the third derivative of the loss at the optimum, the second-derivative recursion has a stationary solution with finite (p/2)-th moment.The second derivative supports a more refined bias expansion.Source: §4.2 · pp. 20–21
• In the logistic-regression illustration, spline interpolation with six internal knots agrees very well with the SGD path, with similar agreement across reruns.The interpolation reconstructs the last iterate as a function of the step size from iterates computed at selected step sizes.Source: §4.2 · pp. 21–22, Figure 2 · p. 21

5.1 Richardson-Romberg Extrapolation

• Using three step sizes, Richardson–Romberg extrapolation cancels the ASGD bias terms of orders gamma and gamma^2.The resulting estimator retains the original ASGD stochastic convergence rate while reducing constant-step-size bias.Source: §5 · p. 22, §5.1 · pp. 22, 24, 25
• Theorem 7 gives a non-asymptotic ASGD bias expansion with explicit gamma and gamma^2 coefficients and an O(gamma^5/2) small-step error.The expansion is derived directly for the stationary law of discrete-time SGD; the transient bias term decays at O(1/k) using the GMC property.Source: §5.1 · pp. 23–24
• The extrapolated ASGD estimator satisfies a quenched CLT and invariance principle, with the invariance principle retaining the oP(n^1/p) approximation rate.These results extend to the linear combination of averaged estimates across step sizes.Source: §5.1 · p. 25

5.2 Online Estimators for Long-Run Covariance Matrices

• Recursive long-run covariance estimators and a bias-reduced variant retain stationary-setting convergence rates for constant-step-size SGD with arbitrary initialization.The paper establishes theoretical guarantees for their use in online inference.Source: §5.2 · pp. 26–27
• Theorem 8 establishes an MSE convergence rate for recursive bΣ_n(γ) estimation of Σ(γ), with η_m=⌊c1m^β⌋ for β>1.The theorem’s assumptions include p=4 and a1γ, a2γ, and a3γ in (0, γ(4)).Source: §5.2 · p. 27
• Theorem 9 gives a convergence-rate result for eΣ_n(γ) under either η_m=⌊c1m^β⌋, τ(m)=⌊c2 log m⌋ (β>1), or η_m=⌊c̄1m log m⌋, τ(m)=⌊c̄2 log m⌋.The stated setting includes p=4 and a1γ, a2γ, and a3γ ∈ (0, γ(4)); the schedule constants satisfy c1>0, c2>0, and c̄1>c̄2>0.Source: §5.2 · pp. 27–28
• Theorem 9(1)’s convergence rate is described as quite sharp, given that parametric-model MSE is typically O(1/n).Source: §5.2 · p. 28

6 Numerical Experiments

• The experiments assess the validity of the proposed online inference methods on simulated data.The two example classes are linear regression and logistic regression.Source: §6 · p. 28

6.1 Linear regression and logistic regression

• The simulated examples use linear regression and penalized logistic regression, with a regularization term added to make the logistic loss strongly convex.The data are generated as i.i.d. observation pairs, and the logistic-loss regularization term is 0.005|θ|2.Source: §6 · p. 28, §6.1 · p. 28

6.2 Empirical Performance of the Online Estimators

• The debiased online estimator outperforms the non-debiased version across the investigated step sizes, and its estimate is closer to the true limiting variance.The reported comparison uses a numerical benchmark computed at iteration n = 10^8; the measurements average 500 independent runs.Source: §6.2 · pp. 28–29

6.3 Coverage Probabilities of Confidence Intervals

• Empirical coverage rates for both estimators converge to the nominal 95%, with enhanced coverage for the debiased version.Table 1 reports results for linear and logistic regression over 500 independent runs; Figure 3 shows linear regression with γ = 0.025.Source: §6.3 · pp. 29–30, Table 1 · p. 30, Figure 3 · p. 30

Funding

• Jiaqi Li’s research was partially supported by NSF DMS-2515926, and Wei Biao Wu received funding from NSF DMS-2610302 and NSF DMS-2311249.These are the funding acknowledgments stated by the authors.Source: Funding · p. 31

Data Availability

• All data are simulated; code for generating the data and reproducing the numerical results is available at https://github.com/jiaqili97/SGD_GMC.The paper identifies the repository as the source of the code.Source: Data Availability · p. 31

Supplemental Material

• The supplement contains covariance-estimator construction and implementation, heavy-tailed and projected-SGD results, proofs, and additional simulations.It also includes additional references.Source: Supplemental Material · p. 37

A Estimation of Long-Run Covariance

• O(γ^2) bias remains after Richardson–Romberg extrapolation cancels the first-order bias.The coefficients are chosen to satisfy equations that cancel the first two bias terms in the distinct-step-size case.Source: A Estimation of Long-Run Covariance · p. 37

A.1 Online Estimator for Long-Run Covariance Matrices

• The recursive long-run covariance estimator requires only O(1) storage and updates its estimate through recursively maintained quantities.The procedure uses a predefined sequence of block endpoints and recursively computes V_n(γ), K_n, H_n(γ), and the ASGD estimate.Source: §A.1 · p. 39

A.2 Bias-Reduced Online Estimator

• Terms with small within-block offsets can have larger bias, motivating their exclusion in the proposed estimator.The estimator uses a sequence of positive integers τ(m) to specify the exclusion.Source: §A.2 · p. 41
• The section defines a bias-reduced counterpart of V_n(γ) for estimating the long-run covariance matrix Σ(γ).The estimator is formed from the extrapolated ASGD sequence and is computed recursively.Source: §A.2 · pp. 41–42

B.1 Quenched α-Stable Convergence

• Under the stated assumptions, ASGD has quenched α-stable convergence from an arbitrary initial point when the gradient-noise tails are regularly varying.The theorem assumes some p in (1, α) and step sizes in (0, γ(p)).Source: §B.1 · pp. 44–45

B.2 Projected SGD

• Projected SGD retains geometric moment contraction when assumptions 1 and 2 hold on a closed convex feasible set containing θ∗.The projection constrains iterates to that set; the stated contraction result applies for p > 1 and γ in (0, γ(p)).Source: §B.2 · pp. 45–46

B.3 Proof of Theorem 10

• The theorem’s quenched α-stable limit holds for any initial point under the proof’s stated contraction and tail assumptions.The proof concludes that S_n/a_n converges weakly to S^(α).Source: §B.3 · p. 47

C.1 Proofs of Theorems 1 & 2

• By induction, the results establish geometric moment contraction and show that the stationary distribution π is unique, independent of θ, and has finite p-th moment; the upper bound for γ is the solution to an equation.Source: §C.1 · pp. 50, 53

C.2 Proof of Theorem 3

• Theorem 3’s proof uses geometric moment contraction to establish asymptotic stationarity and the quenched central limit theorem for any starting point.The iterates can be non-stationary when the initial point does not follow the stationary distribution.Source: §C.2 · p. 56

C.3 Proof of Theorem 4

• For p > 2, the functional-dependence approach yields a best-case Gaussian-approximation rate of n^(1/p) for any initial point.The rate uses the p-th finite-moment condition and follows from geometric contraction’s exponential decay of functional dependence.Source: §C.3 · p. 57
• Theorem 4’s proof concludes that the result holds for an arbitrary initial point, using geometric contraction and partial-sum bounds.The dependence measure is stated to converge exponentially, and the proof bounds the maximal partial sum before concluding the arbitrary-initial-point case.Source: §C.3 · pp. 57–59

C.4 Proofs of Theorems 5 & 6

• For the derivative-error bounds, the proof combines component error terms using a geometric rate ρ⋄ defined to lie in (0, 1).The rate is ρ⋄ = max{ρ1/2◦, eρ1/2, ρ1/2}.Source: §C.4 · p. 64

C.5 Proof of Theorem 7

• The proof derives equations for the unknown moments from stationary SGD iterates, using powers through degree four, Taylor expansions, and exchangeability.The resulting linear system has the form Aγµ = γwγ + O(γ^(5/2)); solving it yields the coefficient of γ^2 in the bias expansion.Source: §C.5 · pp. 65–68
• A0 is nonsingular for every dimension d ≥ 1, so the moment system in (80) can be solved.The proof establishes the result by showing that A0 is block upper triangular and that its diagonal blocks are nonsingular.Source: §C.5 · pp. 70, 72, 75

C.6 Proofs of Theorems 8 and 9

• For Theorem 8, the proof presents the one-dimensional case and omits the multidimensional case, which it says follows by similar arguments.The proof begins with a limit as M → ∞ for the one-dimensional covariance quantities.Source: §C.6 · p. 76
• Theorem proofs consider polynomial and logarithmic choices for η_m and logarithmic τ(m), as well as an η_m proportional to m log m schedule.The second schedule also imposes a condition involving c̄_2 and ρ̄, but the supplied passage truncates the condition.Source: §C.6 · pp. 79–80

D.1 Improved ASGD Estimates by Multiple Step Sizes

• Three SGD step sizes—0.0125, 0.025, and 0.05—are used to form two- and three-step-size extrapolated estimators.Table 3 reports absolute average bias over 100 independent runs, with the penalized population minimizer as the target; the supplied passage does not include its values.Source: §D.1 · p. 81, Table 3 · p. 81

D.2 Comparison of Two Online Estimators of Long-Run Covari-

• For logistic regression, which lacks a closed-form true long-run variance, the estimated value at 0.1 billion steps serves as the baseline.Source: ance · pp. 81–82
• As the iteration step number grows, both proposed online estimators converge to the true long-run variance.Source: ance · p. 82, Figure 5 · p. 82, Figure 6 · p. 83
• The bias-reduced estimator is more accurate than the non-debiased estimator across different step sizes.Source: ance · p. 81, Figure 4 · p. 82

E Additional References

• Related work on iterated Lipschitz maps studies heavy-tailed stationary laws and stable limits for generated sums.Source: E Additional References · p. 84
• The iterated-random-function perspective treats constant-step SGD as a stochastic recursion, with GMC quantitatively controlling dependence on initialization.Source: E Additional References · p. 84