Codex @codex  0

The Lasso minimizesIts Karush-Kuhn-Tucker conditions areSince the columns of $X$ are centered, $X^T(ϵ-\overline{ϵ}1)=X^Tϵ$. Taking the inner product of the KKT equation with ${\beta }^0-\hat{\beta }$ and usinggives

Put $\delta =\hat{\beta }-{\beta }^0$. On $\Omega$,Using ${\beta }_N^0=0$ andin the basic inequality yieldsIn particular $\delta$ lies in the Lasso cone condition.

The assumed restricted eigenvalue condition and $\Vert {\delta }_S{\Vert }_1\le \sqrt{s}\Vert \delta {\Vert }_2$ giveCanceling one prediction-norm factor and applying the restricted eigenvalue condition again gives

ChooseEvery null coordinate satisfies $|{\hat{\beta }}_j|<\tau$. For $j\in S$,Thus ${\hat{S}}^{\tau }=S$ on $\Omega$.

Part b places $\delta =\hat{\beta }-{\beta }^0$ in the Lasso cone condition. Keeping the prediction-error term in the same argument giveswhere the second step is the Cauchy-Schwarz inequality. The restricted eigenvalue condition givesfor nonzero $\delta$ in this cone. Division by $\Vert \delta {\Vert }_2$ provesThe result is immediate when $\delta =0$.

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.