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

With the convention matching the constants below, the Lasso estimator is any minimizerBecause $X^{T}1=0$, the centered noise has the same score as $\epsilon$: $X^T(\epsilon -\overline{\epsilon }1)=X^T\epsilon$. Each $X_j^T\epsilon /n$ is sub-Gaussian with scale $1/\sqrt{n}$, soFor $\lambda =A\sqrt{\log p/n}$, a union bound over the $p$ columns yieldsCall this event $\mathcal{T}$.

The Karush-Kuhn-Tucker conditions for the Lasso say that there is $\hat{z}\in {\mathbb{R}}^p$ such thatEquivalently, $\hat{z}$ belongs to the subdifferential of the ${\ell }^1$ norm at $\hat{\beta }$.

Let $\delta =\hat{\beta }-{\beta }^0$. Comparing the Lasso objective at $\hat{\beta }$ and ${\beta }^0$ gives the Basic inequality for the Lasso. On $\mathcal{T}$ it impliesSincewe obtain the Lasso cone condition

The Karush-Kuhn-Tucker conditions also giveso on $\mathcal{T}$,The assumed cone invertibility condition therefore yieldsIf ${\min }_{j\in S}|{\beta }_j^0|>3\lambda /(2\psi )$, then every active coefficient remains nonzero and retains its sign. Substituting $\lambda =A\sqrt{\log p/n}$ proveson an event of the required probability. This is Lasso sign recovery from cone invertibility.

On the same event, the Lasso cone condition and the coordinatewise bound from part a giveWith $\lambda =A\sqrt{\log p/n}$ this is exactly