Slow-rate prediction bound for the Lasso ($\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2/n\le 4\lambda \Vert {\beta }^0{\Vert }_1$)

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.