mlsanityData to 7 Oct 2026

Accelerating Single-Pass SGD for Generalized Linear Prediction

arXiv 2603.01951 ↗First posted 2 Mar 2026cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study generalized linear prediction under a streaming setting, where each iteration uses only one fresh data point for a gradient-level update. While momentum is well-established in deterministic optimization, a fundamental open question is whether it can accelerate such single-pass non-quadratic stochastic optimization. We propose the first algorithm that successfully incorporates momentum via a novel data-dependent proximal method, achieving dual-momentum acceleration. Our derived excess risk bound decomposes into three components: an improved optimization error, a minimax optimal statistical error, and a higher-order model-misspecification error. The proof handles mis-specification via a fine-grained stationary analysis of inner updates, while localizing statistical error through a two-phase outer-loop analysis. As a result, we resolve the open problem posed by Jain et al. [2018a] and demonstrate that momentum acceleration is more effective than variance reduction for generalized linear prediction in the streaming setting.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 23 of its 41 references that are in the map. First posted on arXiv 2 Mar 2026.

Builds on

23 of 41 references.

References · 23

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  3. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  4. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  5. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  6. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  7. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  8. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  9. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 67
  10. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  11. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  12. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
11 more
  1. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  2. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
  3. 2019Exact minimax risk for linear least squares, and the lower tail of sample covariance matricescited by 34
  4. 2014Competing with the Empirical Risk Minimizer in a Single Passcited by 20
  5. 2013Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimizationcited by 19
  6. 2023Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noisecited by 9
  7. 2023Risk Bounds of Accelerated SGD for Overparameterized Linear Regressioncited by 7
  8. 2024The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimizationcited by 6
  9. 2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6
  10. 2025Optimal Algorithms in Linear Regression under Covariate Shift: On the Importance of Preconditioncited by 3
  11. 2025Learning Curves of Stochastic Gradient Descent in Kernel Regressioncited by 3

Built on by

Not cited yet.