mlsanityData to 7 Oct 2026

Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ

arXiv 2510.19734 ↗First posted 22 Oct 2025cs.LG math.ST stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

Stochastic Gradient Descent (SGD) has become a cornerstone method in modern data science. However, deploying SGD in high-stakes applications necessitates rigorous quantification of its inherent uncertainty. In this work, we establish non-asymptotic Berry--Esseen bounds for linear functionals of online least-squares SGD, thereby providing a Gaussian Central Limit Theorem (CLT) in a growing-dimensional regime. Existing approaches to high-dimensional inference for projection parameters, such as~citechang2023inference, rely on inverting empirical covariance matrices and require at least t gtrsim d3/2 iterations to achieve finite-sample Berry--Esseen guarantees, rendering them computationally expensive and restrictive in the allowable dimensional scaling. In contrast, we show that a CLT holds for SGD iterates when the number of iterations grows as t gtrsim d1+δ for any δ > 0, significantly extending the dimensional regime permitted by prior works while improving computational efficiency. The proposed online SGD-based procedure operates in O(td) time and requires only O(d) memory, in contrast to the O(td2 + d3) runtime of covariance-inversion methods. To render the theory practically applicable, we further develop an online variance estimator for the asymptotic variance appearing in the CLT and establish high-probability deviation bounds for this estimator. Collectively, these results yield the first fully online and data-driven framework for constructing confidence intervals for SGD iterates in the near-optimal scaling regime t gtrsim d1+δ.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 42 of its 76 references that are in the map. First posted on arXiv 22 Oct 2025.

Builds on

42 of 76 references.

References · 42

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  4. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
  5. 2020On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problemscited by 79
  6. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  7. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  8. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 69
  9. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  10. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  11. 2020The Implicit Regularization of Stochastic Gradient Flow for Least Squarescited by 58
  12. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 45
30 more
  1. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 41
  2. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  3. 2016Asymptotic Optimality in Stochastic Optimizationcited by 38
  4. 2020Online Covariance Matrix Estimation in Stochastic Gradient Descentcited by 37
  5. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
  6. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  7. 2021SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticalitycited by 33
  8. 2022On Almost Sure Convergence Rates of Stochastic Gradient Methodscited by 32
  9. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
  10. 2021Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scalingcited by 28
  11. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 26
  12. 2022Homogenization of SGD in high-dimensions: Exact dynamics and generalization propertiescited by 26
  13. 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
  14. 2017Statistical inference using SGDcited by 21
  15. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  16. 2021Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Modelscited by 15
  17. 2023Asymptotic normality and optimality in nonsmooth stochastic approximationcited by 14
  18. 2018HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximationcited by 13
  19. 2024Statistical Inference for Policy Evaluation with Temporal Difference Learningcited by 13
  20. 2017Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCAcited by 11
  21. 2021Bootstrapping the error of Oja's algorithmcited by 11
  22. 2025Statistical inference for Linear Stochastic Approximation with Markovian Noisecited by 11
  23. 2020Stochastic optimization with momentum: convergence, fluctuations, and traps avoidancecited by 10
  24. 2021Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspectivecited by 10
  25. 2021Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithmcited by 6
  26. 2023High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariancecited by 5
  27. 2023Statistical Inference and Large-scale Multiple Testing for High-dimensional Regression Modelscited by 4
  28. 2025Online Covariance Estimation in Nonsmooth Stochastic Approximationcited by 4
  29. 2018Approximate Newton-based statistical inference using only stochastic gradientscited by 3
  30. 2025On the Rate of Gaussian Approximation for Linear Regression Problemscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Statistical Inference on Gradient Flowscited by 0