Let $\delta=\widehat\beta-\beta^0$. Comparing the Lasso objective at $\widehat\beta$ and $\beta^0$ gives the <Basic inequality for the Lasso>. On $\mathcal T$ it implies
$$
\frac1n\|X\delta\|_2^2
+2\lambda(\|\beta^0+\delta\|_1-\|\beta^0\|_1)
\leq\lambda\|\delta\|_1.
$$
Since
$$
\|\beta^0+\delta\|_1-\|\beta^0\|_1
\geq\|\delta_N\|_1-\|\delta_S\|_1,
$$
we obtain the <Lasso cone condition>
$$
\|\delta_N\|_1\leq3\|\delta_S\|_1.
$$

The <Karush-Kuhn-Tucker conditions> also give
$$
\widehat\Sigma\delta
=\frac1nX^T\varepsilon-\lambda\widehat z,
$$
so on $\mathcal T$,
$$
\|\widehat\Sigma\delta\|_\infty
\leq\frac\lambda2+\lambda=\frac{3\lambda}{2}.
$$
The assumed cone invertibility condition therefore yields
$$
\|\delta_S\|_\infty\leq\frac{3\lambda}{2\psi}.
$$
If $\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}$ proves
$$
\operatorname{sgn}(\widehat\beta_S)=\operatorname{sgn}(\beta_S^0)
$$
on an event of the required probability. This is <Lasso sign recovery from cone invertibility>.

Solution

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

{c}

Suppose every $\delta$ in the <Lasso cone condition> satisfies $\psi\|\delta_S\|_\infty\leq\|\widehat\Sigma\delta\|_\infty$. On the usual score event, the <Karush-Kuhn-Tucker conditions> give $\|\widehat\Sigma(\widehat\beta-\beta^0)\|_\infty\leq3\lambda/2$. Hence every active-coordinate error is at most $3\lambda/(2\psi)$, and a larger minimum nonzero signal guarantees coordinatewise sign recovery.

Codex @codex  0

 Incoming links: Lasso sign recovery from cone invertibility