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

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

摘要： 现代从数据中学习的方法依赖于许多调参，例如优化方法中的步长，以及正则化学习方法中的正则化强度。 由于性能可能强烈依赖于这些参数，因此开发 \emph{方法类}之间的比较非常重要，而不仅仅是针对特别调优的参数。 在这里，我们旨在通过 \emph{该类中的最佳方法}的相对性能来比较估计量的类别。 这使我们能够严格量化学习算法的调参敏感性。 作为说明，我们研究了在具有随机各向同性真实参数的标准线性模型中，岭回归在均匀正则化参数网格下的统计估计性能，以及固定步长的梯度下降迭代的性能。 (1) 对于正交设计，我们发现 \emph{精确最小最大最优估计量类}，表明它们等于学习率多项式衰减的梯度下降。 我们找到了岭回归和固定步长梯度下降的精确次优性，表明它们的衰减方式为 $1/k$ 或 $1/k^2$，具体取决于 $k$估计量的特定范围。 (2) 对于具有大量非零特征值的一般设计，我们发现当特征值缓慢衰减时（以指数小于1的幂律形式），梯度下降优于岭回归。 如果特征值快速衰减，以指数大于1的幂律形式或指数形式，则我们发现岭回归优于梯度下降。 我们的结果突出了调参的重要性。 特别是，虽然最优调优的岭回归在我们的情况下是最优估计量，但当两者都被限制在有限的正则化网格上进行调优时，它可能会被梯度下降超越。 显示英文摘要

摘要： Modern methods for learning from data depend on many tuning parameters, such as the stepsize for optimization methods, and the regularization strength for regularized learning methods. Since performance can depend strongly on these parameters, it is important to develop comparisons between \emph{classes of methods}, not just for particularly tuned ones. Here, we take aim to compare classes of estimators via the relative performance of the \emph{best method in the class}. This allows us to rigorously quantify the tuning sensitivity of learning algorithms. As an illustration, we investigate the statistical estimation performance of ridge regression with a uniform grid of regularization parameters, and of gradient descent iterates with a fixed stepsize, in the standard linear model with a random isotropic ground truth parameter. (1) For orthogonal designs, we find the \emph{exact minimax optimal classes of estimators}, showing they are equal to gradient descent with a polynomially decaying learning rate. We find the exact suboptimalities of ridge regression and gradient descent with a fixed stepsize, showing that they decay as either $1/k$ or $1/k^2$ for specific ranges of $k$ estimators. (2) For general designs with a large number of non-zero eigenvalues, we find that gradient descent outperforms ridge regression when the eigenvalues 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 find that ridge regression outperforms gradient descent. Our results highlight the importance of tuning parameters. In particular, while optimally tuned ridge regression is the best estimator in our case, it can be outperformed by gradient descent when both are restricted to being tuned over a finite regularization grid.