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

arXiv: https://arxiv.org/abs/2108.11872 · HTML: https://mlsanity.com/paper/2108.11872/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 69 references that are in the map.
- First posted on arXiv 26 Aug 2021.

## Builds on (most cited first, 19 of 19)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (2020)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [A Continuous-Time View of Early Stopping for Least Squares](https://mlsanity.com/paper/1810.10082/) (2018)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [Asymptotics of Ridge (less) Regression under General Source Condition](https://mlsanity.com/paper/2006.06386/) (2020)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [The Implicit Regularization of Stochastic Gradient Flow for Least Squares](https://mlsanity.com/paper/2003.07802/) (2020)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [Iterate averaging as regularization for stochastic gradient descent](https://mlsanity.com/paper/1802.08009/) (2018)
- [Ridge Regression: Structure, Cross-Validation, and Sketching](https://mlsanity.com/paper/1910.02373/) (2019)
- [Implicit Regularization of Accelerated Methods in Hilbert Spaces](https://mlsanity.com/paper/1905.13000/) (2019)
- [The cost-free nature of optimally tuning Tikhonov regularizers and other ordered smoothers](https://mlsanity.com/paper/1905.12517/) (2019)
- [On the connections between algorithmic regularization and penalization for convex losses](https://mlsanity.com/paper/1909.03371/) (2019)

## Built on by (most cited first, 5 of 5)

- [The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective](https://mlsanity.com/paper/2210.05021/) (2022)
- [Fast Robust Kernel Regression through Sign Gradient Descent with Early Stopping](https://mlsanity.com/paper/2306.16838/) (2023)
- [Double Descent: Understanding Linear Model Estimation of Nonidentifiable Parameters and a Model for Overfitting](https://mlsanity.com/paper/2408.13235/) (2024)
- [Error dynamics of mini-batch gradient descent with random reshuffling for least squares regression](https://mlsanity.com/paper/2406.03696/) (2024)
- [Ridge Regression from Poisson Resetting: A Renewal Perspective on Spectral Regularization](https://mlsanity.com/paper/2605.30059/) (2026)

## Abstract (arXiv)

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.