改进了平均SGD的在线协方差估计，达到最优收敛率。
Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression
- 通过轨迹回归构造新估计器，避免硬截断。
- 理论证明达到最小最大率 $Θ(n^{-(1-α)/2})$。
- 无需海森矩阵信息，适合高维优化场景。
本文研究了Polyak-Ruppert平均随机梯度下降（SGD）中的在线协方差矩阵估计问题。现有批均值估计器在最优学习率指数 $α→1/2^+$ 时收敛率为 $O(n^{-1/8})$。通过逐块偏差分析，重新调整块增长参数后，新估计器收敛率提升至 $O(n^{-(1-α)/3})$，在 $α→1/2^+$ 时可达 $O(n^{-1/6})$。该方法无需海森矩阵信息，保持 $O(d^2)$ 内存开销。我们完整分解误差为方差、平稳性偏差和非线性偏差三部分。进一步提出加权平均变体以避免硬截断。理论上，我们建立了 $Hessian-free$ 协方差估计的最小最大率 $Θ(n^{-(1-α)/2})$：由Le Cam下界得 $Ω(n^{-(1-α)/2})$，而基于轨迹回归的估计器可实现 $O(n^{-(1-α)/2})$，与下界匹配。结果揭示瓶颈在于从SGD漂移中信息积累呈亚线性增长。
原文摘要 · Abstract (English)
We study online covariance matrix estimation for Polyak--Ruppert averaged stochastic gradient descent (SGD). The online batch-means estimator of Zhu, Chen and Wu (2023) achieves an operator-norm convergence rate of $O(n^{-(1-α)/4})$, which yields $O(n^{-1/8})$ at the optimal learning-rate exponent $α\rightarrow 1/2^+$. A rigorous per-block bias analysis reveals that re-tuning the block-growth parameter improves the batch-means rate to $O(n^{-(1-α)/3})$, achieving $O(n^{-1/6})$. The modified estimator requires no Hessian access and preserves $O(d^2)$ memory. We provide a complete error decomposition into variance, stationarity bias, and nonlinearity bias components. A weighted-averaging variant that avoids hard truncation is also discussed. We establish the minimax rate $Θ(n^{-(1-α)/2})$ for Hessian-free covariance estimation from the SGD trajectory: a Le Cam lower bound gives $Ω(n^{-(1-α)/2})$, and a trajectory-regression estimator--which estimates the Hessian by regressing SGD increments on iterates--achieves $O(n^{-(1-α)/2})$, matching the lower bound. The construction reveals that the bottleneck is the sublinear accumulation of information about the Hessian from the SGD drift.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。