
In Theorem REF , we prove a tight upper bound on the expected excess risk of any constrained least squares estimator \(\widehat{\omega }_{b}^{\operatorname{ERM}}\) . We demonstrate that the localized multiplier process is equal to the correlation between the squared noise and the statistical leverage scores of the covariates, a quantity that appears in minimax lower bounds in the well-specified case with independent noise [1]}. In Proposition REF , we construct a distribution for which there exists a least squares solution \(\widehat{\omega }_{b}^{\operatorname{ERM}}\)  whose excess risk is lower-bounded by the localized quadratic process. Hence, both terms appearing in our upper bound are not improvable in general.

In Theorem REF , we prove a tight excess risk upper bound for the ridge regression estimator. We recover the excess risk upper bound proved for constrained least squares, with the localized quadratic term replaced by a bias term that yields a logarithmic improvement.

Section REF  is dedicated to corollaries of our upper bounds. We show that under some assumptions frequently considered in the literature, the localized multiplier process is, up to log factors, upper-bounded by a term of order \(dm^{2}/n\) . Consequently, in such regimes, the constrained least squares and the ridge regression estimators match the rate of the lower bound (REF ) up to logarithmic factors.

In Theorem REF , we construct a distribution \(P\)  with \(r=1\)  and \(m=1\)  such that for \(b \sim \sqrt{d}\) , any constrained least squares estimator \(\widehat{\omega }_{b}^{\operatorname{ERM}}\)  incurs an excess risk that is larger by a \(\sqrt{d}\)  factor than the lower bound (REF ) proved in [2]}. In particular, we refute the conjecture of Ohad Shamir on the optimality of the constrained least squares estimator.

The lower bound (REF ) that only holds for proper linear predictors was matched in [2]} via the non-linear Vovk-Azoury-Warmuth (VAW) forecaster without tuning the regularization parameter. We observe that once the regularization parameter is tuned, the VAW forecaster yields an exponential improvement on the parameters \(b\)  and \(r\)  in the lower bound (REF ); in particular, our observation demonstrates a fundamental gap between the performance achievable by proper and improper estimators. In addition, we discuss a modified version of the VAW forecaster due to [4]} that completely removes the dependence on the boundedness constants \(b\)  and \(r\)  in its excess risk upper bound.

