Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheoryMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Statistical Inference for Low-Rank Tensor Models
Statistical inference for tensors has emerged as a critical challenge in analyzing high-dimensional data in modern data science. This paper introduces a unified framework for inferring general and low-Tucker-rank linear …
regressionOnline Inference in Distributional Temporal-Difference Learning
We study online statistical inference for functionals of the return distribution under a fixed policy. The return distribution is estimated by nonparametric distributional temporal-difference learning from a single Marko…
Statistical Inference for Linear Functionals of Online Least-squares SGD when $t \gtrsim d^{1+δ}$
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,…
Computational EfficiencyInference on Time Series Nonparametric Conditional Moment Restrictions Using General Sieves
General nonlinear sieve learnings are classes of nonlinear sieves that can approximate nonlinear functions of high dimensional variables much more flexibly than various linear sieves (or series). This paper considers gen…
Off-policy evaluationTime SeriesTime Series AnalysisOnline Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data
We study the statistical inference of nonlinear stochastic approximation algorithms utilizing a single trajectory of Markovian data. Our methodology has practical applications in various scenarios, such as Stochastic Gra…
Q-Learningvalid