比较三种线性回归算法的有限样本风险，发现梯度下降始终最优。
Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization
- 通过实例对比分析有限样本风险，揭示算法实际表现差异。
- 梯度下降风险始终优于岭回归，后者在最优调参下仍可能多项式更差。
- 在协方差谱快速衰减的问题上，梯度下降显著优于随机梯度下降。
现有理论表明，在容量与源条件分类的线性回归问题中，梯度下降（GD）始终为极小极大最优，而岭回归与在线随机梯度下降（SGD）对某些问题类别为多项式次优。本文突破极小极大理论框架，对任意良定义的线性回归问题进行实例级的有限样本风险比较。分析得出三项关键发现：第一，GD 优于岭回归——在相近正则化下，GD 的超额风险始终在常数因子内，而岭回归即使在最优调参下也可能多项式更差；第二，GD 与 SGD 不可直接比较——已知某些问题中 GD 可多项式优于 SGD，但本文构造出反例，显示在受良性过拟合理论启发的问题中，最优停止的 GD 可能多项式更差；第三，对于协方差谱快速且连续衰减的一类重要问题（包含满足标准容量条件的所有问题），GD 始终优于 SGD。
原文摘要 · Abstract (English)
Existing theory suggests that for linear regression problems categorized by capacity and source conditions, gradient descent (GD) is always minimax optimal, while both ridge regression and online stochastic gradient descent (SGD) are polynomially suboptimal for certain categories of such problems. Moving beyond minimax theory, this work provides instance-wise comparisons of the finite-sample risks for these algorithms on any well-specified linear regression problem. Our analysis yields three key findings. First, GD dominates ridge regression: with comparable regularization, the excess risk of GD is always within a constant factor of that of ridge, but ridge can be polynomially worse even when tuned optimally. Second, GD is incomparable with SGD. While it is known that for certain problems GD can be polynomially better than SGD, the reverse is also true: we construct problems, inspired by benign overfitting theory, where optimally stopped GD is polynomially worse. Finally, GD dominates SGD for a significant subclass of problems -- those with fast and continuously decaying covariance spectra -- which includes all problems satisfying the standard capacity condition.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。