arXiv:2502.07114stat.MLcs.LG2025-02被引 4

提出在线估计牛顿法协方差矩阵的新方法,实现无需批处理的实时统计推断。

Online Covariance Matrix Estimation in Sketched Newton Methods

  • 基于随机投影构造完全在线的协方差估计器,不依赖矩阵分解。
  • 证明估计器一致且收敛速度为根号n,支持在线统计推断。
  • 适用于带约束问题,在回归和CUTEst测试集上表现更优。

面对流式数据的广泛应用,在线算法在参数估计中日益重要,其中二阶方法因高效稳健而备受关注。本文研究一种在线随机投影牛顿法,通过随机投影技术在每轮迭代中近似执行牛顿步,从而克服传统二阶方法的计算瓶颈。尽管已有研究证明了投影牛顿法的渐近正态性,但其极限协方差矩阵的一致估计仍是一个开放问题。为此,本文提出一种完全在线的协方差矩阵估计器,仅利用牛顿迭代序列构建,无需任何矩阵分解,真正实现无批处理。我们建立了该估计器的一致性和收敛速率,并结合渐近正态性结果,实现了基于投影牛顿法的在线统计推断。此外,还讨论了该估计器向约束问题的扩展,并在回归任务及CUTEst基准测试集上验证了其优越性能。

原文摘要 · Abstract (English)

Given the ubiquity of streaming data, online algorithms have been widely used for parameter estimation, with second-order methods particularly standing out for their efficiency and robustness. In this paper, we study an online sketched Newton method that leverages a randomized sketching technique to perform an approximate Newton step in each iteration, thereby eliminating the computational bottleneck of second-order methods. While existing studies have established the asymptotic normality of sketched Newton methods, a consistent estimator of the limiting covariance matrix remains an open problem. We propose a fully online covariance matrix estimator that is constructed entirely from the Newton iterates and requires no matrix factorization. Compared to covariance estimators for first-order online methods, our estimator for second-order methods is batch-free. We establish the consistency and convergence rate of our estimator, and coupled with asymptotic normality results, we can then perform online statistical inference for the model parameters based on sketched Newton methods. We also discuss the extension of our estimator to constrained problems, and demonstrate its superior performance on regression problems as well as benchmark problems in the CUTEst set.

在线学习牛顿法协方差估计统计推断

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。