Sharp Risk Bounds for Early-stopping in Gaussian Linear Regression

Tobias Wegel, Gil Kur, Patrick Rebeschini
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1792-1800, 2026.

Abstract

We study early-stopped mirror descent (ESMD) for high-dimensional Gaussian linear regression over arbitrary convex bodies and design matrices, where the task is to minimize the in-sample mean squared error. Our main result shows that some of the sharpest risk bounds for the least squares estimator (LSE), based on the local Gaussian width, extend to ESMD. We derive sufficient conditions on the potential, expressed via the Minkowski functional, under which our result holds. These conditions allow us to construct new potentials and analyze existing ones. Our results then yield general sufficient conditions for minimax optimality of ESMD, provide a systematic comparison with the LSE, and establish the tightest known risk bound in the $\ell_1$-constrained setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-wegel26a, title = { Sharp Risk Bounds for Early-stopping in Gaussian Linear Regression }, author = {Wegel, Tobias and Kur, Gil and Rebeschini, Patrick}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1792--1800}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/wegel26a/wegel26a.pdf}, url = {https://proceedings.mlr.press/v300/wegel26a.html}, abstract = { We study early-stopped mirror descent (ESMD) for high-dimensional Gaussian linear regression over arbitrary convex bodies and design matrices, where the task is to minimize the in-sample mean squared error. Our main result shows that some of the sharpest risk bounds for the least squares estimator (LSE), based on the local Gaussian width, extend to ESMD. We derive sufficient conditions on the potential, expressed via the Minkowski functional, under which our result holds. These conditions allow us to construct new potentials and analyze existing ones. Our results then yield general sufficient conditions for minimax optimality of ESMD, provide a systematic comparison with the LSE, and establish the tightest known risk bound in the $\ell_1$-constrained setting. } }
Endnote
%0 Conference Paper %T Sharp Risk Bounds for Early-stopping in Gaussian Linear Regression %A Tobias Wegel %A Gil Kur %A Patrick Rebeschini %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-wegel26a %I PMLR %P 1792--1800 %U https://proceedings.mlr.press/v300/wegel26a.html %V 300 %X We study early-stopped mirror descent (ESMD) for high-dimensional Gaussian linear regression over arbitrary convex bodies and design matrices, where the task is to minimize the in-sample mean squared error. Our main result shows that some of the sharpest risk bounds for the least squares estimator (LSE), based on the local Gaussian width, extend to ESMD. We derive sufficient conditions on the potential, expressed via the Minkowski functional, under which our result holds. These conditions allow us to construct new potentials and analyze existing ones. Our results then yield general sufficient conditions for minimax optimality of ESMD, provide a systematic comparison with the LSE, and establish the tightest known risk bound in the $\ell_1$-constrained setting.
APA
Wegel, T., Kur, G. & Rebeschini, P.. (2026). Sharp Risk Bounds for Early-stopping in Gaussian Linear Regression . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1792-1800 Available from https://proceedings.mlr.press/v300/wegel26a.html.

Related Material