Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization
This work provides instance-wise risk comparisons for practitioners in machine learning, offering insights into algorithm selection, though it is incremental as it builds on existing minimax theory.
The paper compares finite-sample risks of gradient descent (GD), ridge regression, and stochastic gradient descent (SGD) in linear regression, finding that GD consistently outperforms ridge regression and is often better than SGD, with polynomial gaps in risk in some cases.
Existing theory suggests that for linear regression problems categorized by capacity and source conditions, gradient descent (GD) is always minimax optimal, while both ridge regression and online stochastic gradient descent (SGD) are polynomially suboptimal for certain categories of such problems. Moving beyond minimax theory, this work provides instance-wise comparisons of the finite-sample risks for these algorithms on any well-specified linear regression problem. Our analysis yields three key findings. First, GD dominates ridge regression: with comparable regularization, the excess risk of GD is always within a constant factor of ridge, but ridge can be polynomially worse even when tuned optimally. Second, GD is incomparable with SGD. While it is known that for certain problems GD can be polynomially better than SGD, the reverse is also true: we construct problems, inspired by benign overfitting theory, where optimally stopped GD is polynomially worse. Finally, GD dominates SGD for a significant subclass of problems -- those with fast and continuously decaying covariance spectra -- which includes all problems satisfying the standard capacity condition.