Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Consistent Risk Estimation in Moderately High-Dimensional Linear RegressionIEEE Transactions on Information Theory, 2021
- Optimal rates for spectral algorithms with least-squares regression over Hilbert spacesApplied and Computational Harmonic Analysis, 2020
- Optimal Rates for Regularization of Statistical Inverse Learning ProblemsFoundations of Computational Mathematics, 2017
- Early stopping for non-parametric regression: An optimal data-dependent stopping rule2011
- Spectral Analysis of Large Dimensional Random Matrices2010
- Gaussian model selection with an unknown varianceThe Annals of Statistics, 2009
- On Early Stopping in Gradient Descent LearningConstructive Approximation, 2007
- On regularization algorithms in learning theoryJournal of Complexity, 2007
- Convergence Rates of General Regularization Methods for Statistical Inverse Problems and ApplicationsSIAM Journal on Numerical Analysis, 2007
- Gaussian model selectionJournal of the European Mathematical Society, 2001