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

arXiv: https://arxiv.org/abs/2510.19734 · HTML: https://mlsanity.com/paper/2510.19734/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 76 references that are in the map.
- First posted on arXiv 22 Oct 2025.

## Builds on (most cited first, 30 of 42)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [The Implicit Regularization of Stochastic Gradient Flow for Least Squares](https://mlsanity.com/paper/2003.07802/) (2020)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)
- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019)
- [Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT](https://mlsanity.com/paper/1904.02130/) (2019)
- [Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling](https://mlsanity.com/paper/2106.03156/) (2021)
- [Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize](https://mlsanity.com/paper/2106.01257/) (2021)
- [Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties](https://mlsanity.com/paper/2205.07069/) (2022)
- [Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions](https://mlsanity.com/paper/2206.07252/) (2022)
- [Statistical inference using SGD](https://mlsanity.com/paper/1705.07477/) (2017)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models](https://mlsanity.com/paper/2106.03696/) (2021)
- [Statistical Inference for Policy Evaluation with Temporal Difference Learning](https://mlsanity.com/paper/2410.16106/) (2024)
- [Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA](https://mlsanity.com/paper/1712.04332/) (2017)

## Built on by (most cited first, 1 of 1)

- [Statistical Inference on Gradient Flows](https://mlsanity.com/paper/2606.01257/) (2026)

## 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+δ.