标题： 比较估计量类：在线性模型中梯度下降何时优于岭回归？ 显示英文标题

标题： Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?

摘要： 从数据中学习的方法依赖于各种类型的调整参数，例如惩罚强度或步长大小。 由于性能可能强烈依赖这些参数，因此通过考虑预设的有限参数集合来比较估计器类别比仅仅比较特别调优的方法更为重要。 在这项工作中，我们通过类中最佳方法的相对性能来研究方法类别。 我们考虑线性回归的核心问题——随机各向同性真实值，并研究两种基本方法（梯度下降和岭回归）的估计性能。 我们揭示了以下现象。 (1) 对于一般设计，当经验数据协方差矩阵的特征值以小于1的幂律衰减时，固定步长梯度下降优于岭回归。如果相反，特征值以大于1的幂律或指数快速衰减，我们证明岭回归优于梯度下降。 (2) 对于正交设计，我们计算出精确的最小最大最优估计器类别（实现最小-最大-最小最优性），表明它等价于具有衰减学习率的梯度下降。我们发现固定步长的岭回归和梯度下降的次优性。 我们的结果强调统计性能可能强烈依赖调整参数。特别是，虽然最优调优的岭回归是我们设定下最好的估计器，但它可以被梯度下降任意/无界地超过，当两种方法仅在有限多个正则化参数范围内进行调优时。 显示英文摘要

摘要： Methods for learning from data depend on various types of tuning parameters, such as penalization strength or step size. Since performance can depend strongly on these parameters, it is important to compare classes of estimators-by considering prescribed finite sets of tuning parameters-not just particularly tuned methods. In this work, we investigate classes of methods via the relative performance of the best method in the class. We consider the central problem of linear regression-with a random isotropic ground truth-and investigate the estimation performance of two fundamental methods, gradient descent and ridge regression. We unveil the following phenomena. (1) For general designs, constant stepsize gradient descent outperforms ridge regression when the eigenvalues of the empirical data covariance matrix decay slowly, as a power law with exponent less than unity. If instead the eigenvalues decay quickly, as a power law with exponent greater than unity or exponentially, we show that ridge regression outperforms gradient descent. (2) For orthogonal designs, we compute the exact minimax optimal class of estimators (achieving min-max-min optimality), showing it is equivalent to gradient descent with decaying learning rate. We find the sub-optimality of ridge regression and gradient descent with constant step size. Our results highlight that statistical performance can depend strongly on tuning parameters. In particular, while optimally tuned ridge regression is the best estimator in our setting, it can be outperformed by gradient descent by an arbitrary/unbounded amount when both methods are only tuned over finitely many regularization parameters.