Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 41 of its 100 references that are in the map. First posted on arXiv 20 Feb 2023.
Builds on
41 of 100 references.
References · 41
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
- 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
- 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 146
- 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
- 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
- 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 97
- 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
- 2020On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problemscited by 79
- 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
- 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
- 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 69
- 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
29 more
- 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
- 2020The Implicit Regularization of Stochastic Gradient Flow for Least Squarescited by 58
- 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 45
- 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 41
- 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
- 2016Asymptotic Optimality in Stochastic Optimizationcited by 38
- 2020Online Covariance Matrix Estimation in Stochastic Gradient Descentcited by 37
- 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
- 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
- 2021SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticalitycited by 33
- 2022On Almost Sure Convergence Rates of Stochastic Gradient Methodscited by 32
- 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
- 2021Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scalingcited by 28
- 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 26
- 2022Homogenization of SGD in high-dimensions: Exact dynamics and generalization propertiescited by 26
- 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
- 2017Statistical inference using SGDcited by 21
- 2021Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Modelscited by 15
- 2023Asymptotic normality and optimality in nonsmooth stochastic approximationcited by 14
- 2017Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCAcited by 11
- 2021Bootstrapping the error of Oja's algorithmcited by 11
- 2020Stochastic optimization with momentum: convergence, fluctuations, and traps avoidancecited by 10
- 2021Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspectivecited by 10
- 2014Testing and Confidence Intervals for High Dimensional Proportional Hazards Modelcited by 6
- 2021Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithmcited by 6
- 2023Statistical Inference and Large-scale Multiple Testing for High-dimensional Regression Modelscited by 4
- 2018Approximate Newton-based statistical inference using only stochastic gradientscited by 3
- 2018Valid Post-selection Inference in Assumption-lean Linear Regressioncited by 2
- 2020Berry-Esseen Bounds for Projection Parameters and Partial Correlations with Increasing Dimensioncited by 1
Built on by
Citing papers per year: 2023: 1.
1 paper.