Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization (Extended Abstract)

Jingfeng Wu, Peter L. Bartlett, Sham M. Kakade, Jason D. Lee, Bin Yu
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6849-6851, 2026.

Abstract

Existing theory suggests that for linear regression problems categorized by capacity and source conditions, \emph{gradient descent} (GD) is always minimax optimal, while both \emph{ridge regression} and online \emph{stochastic gradient descent} (SGD) are polynomially suboptimal for certain categories of such problems. Moving beyond minimax theory, this work provides \emph{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 \emph{dominates} ridge regression: with comparable regularization, the excess risk of GD is \emph{always} within a constant factor of ridge, but ridge can be \emph{polynomially} worse even when tuned optimally. Second, GD is \emph{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 \emph{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-wu26a, title = {Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization (Extended Abstract)}, author = {Wu, Jingfeng and Bartlett, Peter L. and Kakade, Sham M. and Lee, Jason D. and Yu, Bin}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {6849--6851}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/wu26a/wu26a.pdf}, url = {https://proceedings.mlr.press/v336/wu26a.html}, abstract = {Existing theory suggests that for linear regression problems categorized by capacity and source conditions, \emph{gradient descent} (GD) is always minimax optimal, while both \emph{ridge regression} and online \emph{stochastic gradient descent} (SGD) are polynomially suboptimal for certain categories of such problems. Moving beyond minimax theory, this work provides \emph{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 \emph{dominates} ridge regression: with comparable regularization, the excess risk of GD is \emph{always} within a constant factor of ridge, but ridge can be \emph{polynomially} worse even when tuned optimally. Second, GD is \emph{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 \emph{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.} }
Endnote
%0 Conference Paper %T Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization (Extended Abstract) %A Jingfeng Wu %A Peter L. Bartlett %A Sham M. Kakade %A Jason D. Lee %A Bin Yu %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-wu26a %I PMLR %P 6849--6851 %U https://proceedings.mlr.press/v336/wu26a.html %V 336 %X Existing theory suggests that for linear regression problems categorized by capacity and source conditions, \emph{gradient descent} (GD) is always minimax optimal, while both \emph{ridge regression} and online \emph{stochastic gradient descent} (SGD) are polynomially suboptimal for certain categories of such problems. Moving beyond minimax theory, this work provides \emph{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 \emph{dominates} ridge regression: with comparable regularization, the excess risk of GD is \emph{always} within a constant factor of ridge, but ridge can be \emph{polynomially} worse even when tuned optimally. Second, GD is \emph{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 \emph{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.
APA
Wu, J., Bartlett, P.L., Kakade, S.M., Lee, J.D. & Yu, B.. (2026). Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization (Extended Abstract). Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:6849-6851 Available from https://proceedings.mlr.press/v336/wu26a.html.

Related Material