 Slow-rate prediction bound for the Lasso

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