Statistical Inference for Linear Functionals of Online Least-squares SGD when t ≳ d 1 + δ t\gtrsim d^{1+\delta}
Bhavya Agrawalla, Krishnakumar Balasubramanian, Promit Ghosal · 2025
Read Statistical Inference for Linear Functionals of Online Least-squares SGD when t ≳ d 1 + δ t\gtrsim d^{1+\delta} by Bhavya Agrawalla, Krishnakumar Balasubramanian, Promit Ghosal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19734.txt.
Introduction
Bhavya Agrawalla, Krishnakumar Balasubramanian, and Promit Ghosal build the first fully online framework for confidence intervals around stochastic gradient descent estimates in high dimensions. High-stakes uses of SGD need honest measures of uncertainty. But past theory demands far more steps, relative to the size of the problem. It also needs large covariance matrices inverted, which is costly.
The authors prove non-asymptotic Berry-Esseen bounds for linear functionals of online least-squares SGD iterates. That gives a Gaussian limit under a much weaker growth condition on steps versus problem size. Their procedure runs in time linear in the size per step and stores only a vector. They add an online estimator for the asymptotic variance, with high-probability error bounds. The package makes data-driven uncertainty checks for SGD practical.
Catalog record
| CREATOR | Bhavya Agrawalla, Krishnakumar Balasubramanian, Promit Ghosal |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 158 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-19734
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Statistical Inference for Linear Functionals of Online Least-squares SGD when t ≳ d 1 + δ t\gtrsim d^{1+\delta} Bhavya Agrawalla, Krishnakumar Balasubramanian, Promit Ghosal Abstract . 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 [ 16 ] , rely on inverting empirical covariance matrices and require at least t ≳ d 3 / 2 t\gtrsim d^{3/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 ≳ d 1 + δ t\gtrsim d^{1+\delta} for any δ > 0 \delta>0 , significantly extending the dimensional regime permitted by prior works while improving computational efficiency. The proposed online SGD-based procedure operates in 𝒪 ( t d ) \mathcal{O}(td) time and requires only 𝒪 ( d ) \mathcal{O}(d) memory, in contrast to the 𝒪 ( t d 2 + d 3 ) \mathcal{O}(td^{2}+d^{3}) 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 ≳ d 1 + δ t\gtrsim d^{1+\delta} . 1. Introduction Stochastic gradient descent [ 56 ] is a popular optimization algorithm widely used in data science. It is a stochastic iterative method for minimizing the expected loss function by updating model parameters based on the (stochastic) gradient of the loss with respect to the parameters obtained from a random sample. SGD is widely used for training linear and logistic regression models, support vector machines, deep neural networks, and other such machine learning models on large-scale datasets. Because of its simplicity and effectiveness, SGD has become a staple of modern data science and machine learning, and has been continuously improved and extended to handle more complex scenarios. Despite its wide-spread applicability for prediction and point estimation, quantifying the uncertainty associated with SGD is not well-understood. Indeed, uncertainty quantification is a key component of decision making systems, ensuring the credibility and validity of data-driven findings; see, for e.g., [ 17 ] , for a concrete medical application where it is not enough to just optimize SGD to obtain prediction performance but is more important to quantify the associated uncertainty. Developing an inferential theory for SGD becomes more challenging in particular in the growing-dimensional setting, when the number of parameters can grow with the number of iterations (or equivalently the number of observations used in online SGD). Such growing-dimensional settings are common in modern statistical machine learning problems and it well-known that online SGD has implicit regularization properties, as examined in several recent works including [ 1 , 68 , 74 , 70 , 19 ] . A crucial step toward developing an inferential theory of SGD is to establish central limit theorems (CLT) and related normal approximation results. Such results in-turn could be used to develop practical inferential procedures. Towards that, in this paper, we establish growing-dimensional CLTs and develop statistical inference methodology for linear functionals of online SGD iterates. Specifically, we focus on the misspecified linear regression model comprised of a random vector of covariates X\in\mathbb{R}^{d} and a scalar random variable Y . It is well known that the best linear L_{2} approximation to Y is the linear functional (\beta^{*})^{\top}X , where \displaystyle\textstyle\beta^{*}:=\min_{\theta\in\mathbb{R}^{d}}\mathbb{E}[(Y-\langle X,\theta\rangle)^{2}]. In order to estimate the parameter \beta^{*}\in\mathbb{R}^{d} , we consider minimizing the above population loss function using online SGD with an initial guess \theta_{0}\in\mathbb{R}^{d} . Here, \langle\cdot,\cdot\rangle represents the Euclidean inner-product. Letting the i^{\textrm{th}} random observation be (X_{i},Y_{i}) and the step-size at the i^{\textrm{th}} iterate be \eta_{i} , the online SGD update rule is given by (1) \displaystyle\theta_{i}:=\theta_{i-1}+\eta_{i}X_{i}(Y_{i}-\langle X_{i},\theta_{i-1}\rangle). We emphasize here that the online SGD uses one observation per iteration, and the observations are assumed to be independent and identically distributed across the iterations. Hence, suppose we run it for t iterations, then the overall number of observations used is also t . Letting a\in\mathbb{R}^{d} be a d -dimensional deterministic vector, we wish to establish a central limit theorem for the following linear functional \langle a,\theta_{t}\rangle . Technically, in the above discussion we consider a growing dimensional setup in which the dimension d changes with t . We simply use d instead of d_{t} for notational convenience. Our Contributions. We make the following contributions in this work. (1) We establish a growing-dimensional Central Limit Theorem (CLT) in the form of Berry–Esseen bounds for linear functionals of the least-squares online SGD iterates in ( 1 ). Our main result, stated informally below (and rigorously in Theorem 2.3 ), provides a finite-sample Gaussian approximation under mild moment and scaling assumptions. Informal Statement. Consider the least-squares online SGD update ( 1 ) run for t steps with step size \eta_{i}=\frac{\eta}{\sqrt{d}\,i^{\alpha}} for some \eta>0 and \alpha\in(\tfrac{1}{2},1) . Suppose further that • \displaystyle\lim_{t,d\to\infty}(\log t+\log d)^{2}d^{1/2}t^{-(1-\alpha)}=0 , • X and \epsilon:=Y-X^{\top}\beta^{*} have finite moments of order 4p , for some absolute constant p\geq 2 . Then there exist absolute constants C_{1},C_{2}>0 such that, for all t,d\geq C_{1} , (2) \displaystyle\sup_{\gamma\in\mathbb{R}}\bigg|\mathbb{P}\!\left(\frac{\langle a,\theta_{t}\rangle-\langle a,\beta^{*}\rangle}{\sqrt{\Var(\langle a,\theta_{t}\rangle)}}\leq\gamma\right)-\Phi(\gamma)\bigg|\;\lesssim\;C_{2}(dt^{-2\alpha})^{\frac{p}{8p+4}}, where \Phi(\cdot) denotes the CDF of the standard normal distribution. (2) To make the bound in ( 2 ) practical for inference, we propose a sub-sampling–based online estimator for the variance term, described in Section 3 . We show in Theorem 3.1 that the additional estimation error is negligible. This yields the first fully data-driven, online framework for growing-dimensional algorithmic inference using stochastic optimization methods such as SGD, operating under the near-optimal scaling t\gtrsim d^{1+\delta} for any \delta>0 . Our results are conceptually related to recent work on finite-sample normal approximation in high-dimensional regression, notably [ 16 ] , which obtained Berry–Esseen bounds for projection parameters under general moment assumptions but required t\gtrsim d^{3/2} . In contrast, we achieve the same inferential objective under the significantly improved scaling t\gtrsim d^{1+\delta} (by choosing \alpha such that \frac{1}{2}<\alpha<\frac{1+2\delta}{2+2\delta} ), without imposing stronger assumptions. Moreover, our approach is computationally and memory efficient, running in \mathcal{O}(td) time and \mathcal{O}(d) space, compared to \mathcal{O}(td^{2}+d^{3}) for covariance-inversion–based methods that require explicit matrix inversion. These theoretical and algorithmic advantages make our method scalable to substantially higher-dimensional regimes. Section H provides a detailed discussion of the key methodological ingredients enabling this improved scaling. Beyond providing a theoretical framework for growing-dimensional inference, our results have practical implications for constructing algorithmic prediction intervals in linear regression. For a new test point a , independent of the training data used by SGD, choosing a in ( 2 ) directly yields a predictive confidence interval, complementing prior works on implicit regularization and benign overfitting [ 1 , 68 , 74 , 70 , 19 ] . Furthermore, our results can be used to develop algorithmic Wald-type tests