Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?
This work addresses the statistical performance comparison of fundamental estimators for researchers in machine learning and statistics, providing theoretical insights into when gradient descent can beat ridge regression, though it is incremental as it builds on existing linear model analysis.
The paper tackles the problem of comparing estimator classes in linear regression by analyzing the relative performance of gradient descent and ridge regression under different eigenvalue decay conditions, showing that gradient descent outperforms ridge regression when eigenvalues decay slowly (power law exponent <1) and ridge regression is better when decay is fast (exponent >1 or exponential). For orthogonal designs, it finds that gradient descent with decaying learning rate is minimax optimal, while ridge regression and constant-step gradient descent are suboptimal.
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.