# Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 100 references that are in the map.
- First posted on arXiv 20 Feb 2023.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (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)
- [Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models](https://mlsanity.com/paper/2106.03696/) (2021)

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

- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)

## Abstract (arXiv)

Stochastic gradient descent (SGD) has emerged as the quintessential method in a data scientist's toolbox. Using SGD for high-stakes applications requires, however, careful quantification of the associated uncertainty. Towards that end, in this work, 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. We first show that a bias-corrected CLT holds when the number of iterations of the online SGD, t, grows sub-linearly in the dimensionality, d. In order to use the developed result in practice, we further develop an online approach for estimating the variance term appearing in the CLT, and establish high-probability bounds for the developed online estimator. Together with the CLT result, this provides a fully online and data-driven way to numerically construct confidence intervals. This enables practical high-dimensional algorithmic inference with SGD and to the best of our knowledge, is the first such result.