Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 205 / 6 / Solution

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$.