Statistical Guarantees for High-Dimensional Stochastic Gradient Descent

• URL: http://arxiv.org/abs/2510.12013v1
• Date: Mon, 13 Oct 2025 23:27:56 GMT
• Title: Statistical Guarantees for High-Dimensional Stochastic Gradient Descent
• Abstract summary: We provide rigorous statistical guarantees for constant learning-rate SGD and ASGD in high-dimensional regimes.<n>Our proposed framework offers a novel toolkit for analyzing a broad class of high-dimensional learning algorithms.
• Score: 9.729147728224946
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic Gradient Descent (SGD) and its Ruppert-Polyak averaged variant (ASGD) lie at the heart of modern large-scale learning, yet their theoretical properties in high-dimensional settings are rarely understood. In this paper, we provide rigorous statistical guarantees for constant learning-rate SGD and ASGD in high-dimensional regimes. Our key innovation is to transfer powerful tools from high-dimensional time series to online learning. Specifically, by viewing SGD as a nonlinear autoregressive process and adapting existing coupling techniques, we prove the geometric-moment contraction of high-dimensional SGD for constant learning rates, thereby establishing asymptotic stationarity of the iterates. Building on this, we derive the $q$-th moment convergence of SGD and ASGD for any $q\ge2$ in general $\ell^s$-norms, and, in particular, the $\ell^{\infty}$-norm that is frequently adopted in high-dimensional sparse or structured models. Furthermore, we provide sharp high-probability concentration analysis which entails the probabilistic bound of high-dimensional ASGD. Beyond closing a critical gap in SGD theory, our proposed framework offers a novel toolkit for analyzing a broad class of high-dimensional learning algorithms.

Related papers

• Factor Augmented High-Dimensional SGD [4.542148087324063]
  gradient descent (SGD) is a fundamental optimization algorithm widely used in modern machine learning.<n>We propose Factor-Augmented SGD (FSGD), a new optimization method that leverages latent factor representations in high-dimensional learning tasks.
  arXiv  Detail & Related papers  (2026-05-19T03:10:33Z)
• Interactive Learning of Single-Index Models via Stochastic Gradient Descent [15.788049354466715]
  gradient descent (SGD) is a cornerstone algorithm for high-dimensional optimization.<n>Recent theoretical advances have provided a deep understanding of how SGD enables feature learning in high-dimensional nonlinear models.
  arXiv  Detail & Related papers  (2026-02-19T22:22:45Z)
• High-Dimensional Limit of Stochastic Gradient Flow via Dynamical Mean-Field Theory [6.2000582635449994]
  Modern machine learning models are typically trained via multi-pass gradient descent (SGD) with small batch sizes.<n>We analyze the high-dimensional dynamics of a differential equation called a emphstochastic gradient flow (SGF)<n>We show that the resulting DMFT equations recover several existing high-dimensional descriptions of SGD dynamics as special cases.
  arXiv  Detail & Related papers  (2026-02-06T02:37:10Z)
• The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization [4.7256945641654164]
  gradient descent (SGD) is a widely used algorithm in machine learning, particularly for neural network training. Recent studies on SGD for canonical quadratic optimization or linear regression show it attains well generalization under suitable high-dimensional settings. This paper investigates SGD with two essential components in practice: exponentially decaying step size schedule and momentum.
  arXiv  Detail & Related papers  (2024-09-15T14:20:03Z)
• Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape [4.73194777046253]
  Gradient Descent (SGD) is an out-of-equilibrium algorithm used extensively to train artificial neural networks. We show that SGD largely outperforms GD for sufficiently small batch sizes.
  arXiv  Detail & Related papers  (2023-09-09T13:29:17Z)
• Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression [14.521929085104441]
  gradient descent (SGD) has emerged as the quintessential method in a data scientist's toolbox.<n>We establish a high-dimensional Central Limit Theorem (CLT) for linear functionals of online SGD iterates for overparametrized least-squares regression with non-isotropic Gaussian inputs.<n>We develop an online approach for estimating the variance term appearing in the CLT, and establish high-probability bounds for the developed online estimator.
  arXiv  Detail & Related papers  (2023-02-20T02:38:36Z)
• NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer [45.47667026025716]
  We propose a novel, robust and accelerated iteration that relies on two key elements. The convergence and stability of the obtained method, referred to as NAG-GS, are first studied extensively. We show that NAG-arity is competitive with state-the-art methods such as momentum SGD with weight decay and AdamW for the training of machine learning models.
  arXiv  Detail & Related papers  (2022-09-29T16:54:53Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  We study to what extent may gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining a good fit training data. We analyze the closely related with-replacement SGD, for which an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate.
  arXiv  Detail & Related papers  (2022-02-27T13:25:01Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• On the Generalization of Stochastic Gradient Descent with Momentum [58.900860437254885]
  We first show that there exists a convex loss function for which algorithmic stability fails to establish generalization guarantees. For smooth Lipschitz loss functions, we analyze a modified momentum-based update rule, and show that it admits an upper-bound on the generalization error. For the special case of strongly convex loss functions, we find a range of momentum such that multiple epochs of standard SGDM, as a special form of SGDEM, also generalizes.
  arXiv  Detail & Related papers  (2021-02-26T18:58:29Z)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  This paper attempts to characterize the particular regularization effect of SGD in the moderate learning rate regime. We show that SGD converges along the large eigenvalue directions of the data matrix, while GD goes after the small eigenvalue directions.
  arXiv  Detail & Related papers  (2020-11-04T21:07:52Z)
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence [30.393999722555154]
  We propose a variant of the classical Polyak step-size (Polyak, 1987) commonly used in the subgradient method. The proposed Polyak step-size (SPS) is an attractive choice for setting the learning rate for gradient descent.
  arXiv  Detail & Related papers  (2020-02-24T20:57:23Z)
• Momentum Improves Normalized SGD [51.27183254738711]
  We show that adding momentum provably removes the need for large batch sizes on objectives. We show that our method is effective when employed on popular large scale tasks such as ResNet-50 and BERT pretraining.
  arXiv  Detail & Related papers  (2020-02-09T07:00:54Z)
• On the Generalization of Stochastic Gradient Descent with Momentum [84.54924994010703]
  momentum-based accelerated variants of gradient descent (SGD) are widely used when training machine learning models. We first show that there exists a convex loss function for which the stability gap for multiple epochs of SGD with standard heavy-ball momentum (SGDM) becomes unbounded. For smooth Lipschitz loss functions, we analyze a modified momentum-based update rule, i.e., SGD with early momentum (SGDEM) under a broad range of step-sizes.
  arXiv  Detail & Related papers  (2018-09-12T17:02:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.