Early-Stopped Mirror Descent for Linear Regression over Convex Bodies
This provides a theoretical guarantee for early-stopping in high-dimensional regression, addressing a gap in understanding for overparameterized regimes, though it is incremental as it builds on existing comparisons.
The paper tackles the question of whether early-stopped iterative optimization can be less statistically efficient than explicit regularization for linear regression with convex constraints, showing that early-stopped mirror descent achieves worst-case risk at most a constant factor times that of the constrained least squares estimator.
Early-stopped iterative optimization methods are widely used as alternatives to explicit regularization, and direct comparisons between early-stopping and explicit regularization have been established for many optimization geometries. However, most analyses depend heavily on the specific properties of the optimization geometry or strong convexity of the empirical objective, and it remains unclear whether early-stopping could ever be less statistically efficient than explicit regularization for some particular shape constraint, especially in the overparameterized regime. To address this question, we study the setting of high-dimensional linear regression under additive Gaussian noise when the ground truth is assumed to lie in a known convex body and the task is to minimize the in-sample mean squared error. Our main result shows that for any convex body and any design matrix, up to an absolute constant factor, the worst-case risk of unconstrained early-stopped mirror descent with an appropriate potential is at most that of the least squares estimator constrained to the convex body. We achieve this by constructing algorithmic regularizers based on the Minkowski functional of the convex body.