Slow-rate prediction bound for the Lasso
= Slow-rate prediction bound for the Lasso
{title2=$\|X(\widehat\beta-\beta^0)\|_2^2/n\leq4\lambda\|\beta^0\|_1$}
For $Y=X\beta^0+\eta$, the <Lasso> objective $\|Y-X\beta\|_2^2/(2n)+\lambda\|\beta\|_1$ has this prediction bound whenever $\|X^T\eta\|_\infty/n\leq\lambda$. Compare its value at $\widehat\beta$ and $\beta^0$, apply <Holder inequality> to the score, and use the triangle inequality. No <restricted eigenvalue condition> is required.