在高维在线学习中，用更少迭代次数实现可信的统计推断。
Statistical Inference for Linear Functionals of Online Least-squares SGD when $t \gtrsim d^{1+δ}$
- 基于在线最小二乘SGD，提出新方法实现高维推断
- 仅需t ≳ d¹⁺δ次迭代即可保证渐近正态性，优于旧方法
- 可实时计算置信区间，适合高维在线场景
随机梯度下降（SGD）已成为现代数据科学的核心方法。但在高风险应用中，必须严格量化其内在不确定性。本文为在线最小二乘SGD的线性泛函建立了非渐近的Berry--Esseen界，首次在增长维度下实现高维统计推断的中心极限定理（CLT）。相比依赖经验协方差矩阵求逆的现有方法（如chang2023inference），这些方法需至少t ≳ d³⁄²次迭代才能获得有限样本的Berry--Esseen保证，计算开销大且维度扩展受限。而本文证明，在t ≳ d¹⁺δ（任意δ>0）时，SGD迭代仍满足CLT，显著拓展了允许的维度范围，并提升计算效率。所提在线方法时间复杂度为O(td)，内存仅需O(d)，远优于协方差求逆法的O(td² + d³)。为使理论实用化，我们进一步设计了在线方差估计器，并建立了该估计器的高概率偏差界。综上，本工作首次实现了在近最优迭代尺度t ≳ d¹⁺δ下的完全在线、数据驱动的置信区间构造框架。
原文摘要 · Abstract (English)
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 \emph{non-asymptotic Berry--Esseen bounds} for linear functionals of online least-squares SGD, thereby providing a Gaussian Central Limit Theorem (CLT) in a \emph{growing-dimensional regime}. Existing approaches to high-dimensional inference for projection parameters, such as~\cite{chang2023inference}, rely on inverting empirical covariance matrices and require at least $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 \gtrsim d^{1+δ}$ for any $δ> 0$, significantly extending the dimensional regime permitted by prior works while improving computational efficiency. The proposed online SGD-based procedure operates in $\mathcal{O}(td)$ time and requires only $\mathcal{O}(d)$ memory, in contrast to the $\mathcal{O}(td^2 + d^3)$ runtime of covariance-inversion methods. To render the theory practically applicable, we further develop an \emph{online variance estimator} for the asymptotic variance appearing in the CLT and establish \emph{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 d^{1+δ}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。