Title: Optimistic lower bounds for convex regularized least-squares,
Abstract: Minimax lower bounds are pessimistic in nature: for any given estimator,
minimax lower bounds yield the existence of a worst-case target vector
$\beta^*_{worst}$ for which the prediction error of the given estimator is
bounded from below. However, minimax lower bounds shed no light on the
prediction error of the given estimator for target vectors different than
$\beta^*_{worst}$. A characterization of the prediction error of any convex
regularized least-squares is given. This characterization provide both a lower
bound and an upper bound on the prediction error. This produces lower bounds
that are applicable for any target vector and not only for a single, worst-case
$\beta^*_{worst}$. Finally, these lower and upper bounds on the prediction
error are applied to the Lasso is sparse linear regression. We obtain a lower
bound involving the compatibility constant for any tuning parameter, matching
upper and lower bounds for the universal choice of the tuning parameter, and a
lower bound for the Lasso with small tuning parameter.