CS Paper Radar

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

Younghun Lee, Jake Zummo, Wei Biao Wu

cs.LG stat.ML ·submitted 2026-10-12 01:07 UTC · v1

Abstract

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.

Comment
42 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Stochastic Gradient Descent: A Nonlinear Time Series Perspective

cs.LG stat.MLmath.ST ·2026-10-14 ·Jiaqi Li, Zhipeng Lou, Stefan Richter, Wei Biao Wu
publishedtheoryhighly cited similarity 0.69
Abstract · 87 pages, 8 figures, accepted to JRSSB

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.

0.51

Strong Gaussian Approximation of Constant Learning Rate SGD: Bias and Trajectory Inference

cs.LG stat.ML ·2026-10-10 ·Joseph Keslin, Wei Biao Wu
similarity 0.67
Abstract

This paper develops strong Gaussian approximations (KMT type) for constant learning rate stochastic gradient descent (SGD). We work with heavy tailed noise and assume that the number of iterates grows and the learning rate shrinks simultaneously. Our work constructs simple Gaussian processes on the same space and bounds, in probability, the maximum difference between the SGD errors and their respective limits. While there exist central limit theorems for constant rate SGD centered at the optimum, these only provide individual iterate inference. By contrast, our quenched KMT approximations allow for finite sample, simultaneous, whole-trajectory-level inference and imply stochastic process convergence (Functional Central Limit Theorems (FCLTs)). For accumulated errors centered at the true optimum, we first obtain a KMT-type approximation bound when the learning rate scales as $γ_n=\frac{c}{\sqrt n}+o(n^{-1/2})$ for a constant $c \in \mathbb{R}^+$ and $n$ iterations. The result reveals a trade off between controlling the bias of SGD and the initialization effect, with no learning rate scaling generally making both contributions vanish in the accumulated error limit. To eliminate these contributions, we consider a Burn in scheme and Richardson-Romberg extrapolation and prove respective KMT and FCLT theorems. We also prove a finite-horizon KMT-type approximation and FCLT for the rescaled iterate trajectory to a stationary Ornstein--Uhlenbeck (OU) process. We consider applications in risk control and simultaneous inference and perform simulations to illustrate our results.

0.22

Limit Theory for Online Expectile Estimation under Short and Long Range Dependence

cs.LG stat.MLmath.ST ·2026-10-12 ·Younghun Lee, Jake Zummo, Wei Biao Wu
similarity 0.65
Abstract · 36 pages, 1 figure

Expectiles are tail-sensitive distributional summaries with important applications in financial risk measurement and forecasting, yet statistical theory for their online estimation from dependent data remains limited. We study a one-pass, stochastic-gradient algorithm with constant learning rate $γ$ for estimating the marginal expectile of a stationary causal process. The recursion admits a unique stationary causal solution and geometrically forgets its initialization. Under short-range dependence, its last iterate is asymptotically Gaussian at the $\sqrtγ$ scale, with variance governed by the population curvature and the long-run variance of the expectile score. For long-memory linear processes the scale changes to $γ^{β-1/2}\ell(1/γ)$, with a Gaussian limit arising from a fractional Brownian motion integral. We further derive the joint long-memory limit for multiple expectile levels and characterize its limiting covariance structure. Various numerical experiments corroborate the predicted Gaussian approximations and regime-specific fluctuation scales.

0.29

Stochastic learning flow: moment equations for stochastic gradient descent at finite step size

cs.LG cond-mat.dis-nn ·2026-10-30 ·Christian Schmid, James M Murray
similarity 0.63
Abstract

Analytical theories of learning in deep networks often assume gradient flow, discarding the finite step size and batch noise of stochastic gradient descent (SGD). Starting from the discrete update, we derive continuous-time equations for the mean and covariance of the parameter distribution under a Gaussian closure for a general stochastic learning, to first order in the learning rate $η$. Applying these stochastic learning flow (SLF) equations to SGD, we show that the mean descends an effective loss regularized by the covariance and loss curvature, while the covariance, unlike in stochastic differential equation approximations, becomes unstable at curvature $2/η$. In SGD ensembles of linear and nonlinear networks, SLF predicts learning curves and mean trajectories more accurately than gradient flow and captures the covariance dynamics, failing where the parameter distribution becomes strongly non-Gaussian. In the full-batch limit, the edge of stability corresponds to a stationary point of the coupled sharpness-covariance dynamics, recovering self-stabilization and central flow, and batch-to-batch curvature fluctuations lower this threshold under SGD.

0.41

Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise

cs.LG math.OCmath.PR ·2026-09-10 ·Amartya Mukherjee, Jun Liu
publishedtheoryhot direction similarity 0.61
Abstract

Stochastic gradient descent (SGD) with gradient clipping and additive noise has become a standard technique for training machine learning models, particularly in applications requiring robustness or privacy guarantees. However, clipping introduces a bias in stochastic gradients, while additive noise introduces additional variance, making the long-run behaviour of individual optimization trajectories difficult to characterize. In this work, we prove that SGD with clipping and additive Gaussian noise (SGD-CN) converges almost surely (a.s.) under smoothness and uniformly bounded stochastic-gradient noise assumptions, provided the step sizes satisfy some standard decaying conditions. Our analysis extends to momentum variants such as the stochastic heavy ball and Nesterov's accelerated gradient, where we show that careful energy constructions yield similar guarantees. These results provide stronger theoretical foundations for understanding the pathwise behaviour of clipped stochastic gradient methods and suggest that, despite the bias and noise introduced by clipping and perturbation, the algorithm remains stable in both convex and nonconvex regimes.

0.56

Exact information accounting for SGD methods

cs.LG cs.ITmath.OCstat.ML ·2026-09-30 ·Akshay Balsubramani
similarity 0.60
Abstract

As an alternative to the standard geometric analyses, we give an exact, information-theoretic analysis of stochastic gradient descent (SGD) and its variants. We show that a preconditioned SGD step is the posterior-mean update of a Gaussian Bayes model, and that its one-step regret splits into an intrinsic-time cost and a change in comparator information. The split extends to an identity for the objective itself. Convex convergence, strict-saddle-point escape, the link between flatness and generalization, the standard learning-rate schedules, adaptive optimizers, and the noisy, momentum, heavy-tailed, and gradient-free variants of SGD each correspond to a term or a special case of this identity. We measure its terms on synthetic and real training runs. On real networks it attributes the slack of classical convergence bounds to the terms their derivations drop and separates optimizers that reach the same training loss. That separation follows the number and consistency of their steps. Its relation to which of them generalizes better differs between networks. For gradient-free SGD the identity determines how a curvature preconditioner should enter the update. The sharpness-based generalization certificate it yields, with a data-independent isotropic prior, is vacuous at network scale unless the curvature spectrum is nearly flat across all parameters.

0.20

Speed limits for information acquisition in stochastic learning dynamics

cs.LG cond-mat.stat-mechstat.ML ·2026-09-08 ·Shuta Kobayashi, Andreas Dechant
theoryhot direction similarity 0.60
Abstract · 15 pages, 4 figures

Neural networks acquire internal representations through learning. In this work, we formulate stochastic gradient descent (SGD) as a Markovian stochastic process and derive a Fisher-information flow speed limit that bounds the rate at which trainable parameters can acquire information about data-generating parameters. The resulting inequality decomposes the upper bound on the information flow into drift and noise contributions, thereby quantifying the roles of deterministic learning forces and SGD-induced fluctuations from an information-theoretic perspective. We verify the bound in analytically tractable basis-function linear regression, where the information budget predicted by the bound reproduces the ordering and characteristic time scales with which different data-generating parameters are encoded in the learned parameters. These results establish Fisher-information speed limits as a quantitative framework for understanding which properties of the data-generating process are acquired, in what order, and how rapidly they can be encoded in the trainable parameters.

0.33

High-dimensional limit theorems for adaptive variants of SGD I: Ballistic limits

cs.LG stat.MLmath.PRmath.ST ·2026-11-14 ·Aukosh Jagannath, Varnan Sarangian
theory similarity 0.60
Abstract

We develop the high-dimensional effective dynamics for adaptive, momentum-based variants of Stochastic Gradient Descent (SGD). These effective dynamics are given by a Markov process. They key observation is that the non-Markovianity in the algorithm due to the exponential moving average and preconditioning can be treated using the method of averaging. Our approach applies to a broad class of algorithms including to Adaptive momentum estimation (ADAM), Momentum orthogonalized by Newton-Schultz (MUON), and its variants. It also applies to a broad class of learning tasks, such at tensor PCA, Gaussian projective models, teacher-student networks, and a multi-layer neural network trained on the XOR problem using a hybrid of MUON and ADAM as commonly done in practice. We demonstrate how to this technique can give precise, quantitative comparisons between algorithms. In particular, we find interesting phenomena, such as the cross-over phenomenon where online SGD has better generalization than ADAM early in training until the learning curves cross and ADAM dominates. Furthermore, we prove a version of the Edge of Stability phenomenon. In particular, we introduce an analogue of the infinity Laplacian that sharply characterizes the Edge of Stability.

0.07