= Solution
Because $\lVert X_j\rVert_2=\sqrt n$, each coordinate of $X^T\varepsilon/n$ is $N(0,\sigma^2/n)$. The <Gaussian tail bound> and a <union bound> give
$$
\mathbb P\left(\left\lVert\frac{X^T\varepsilon}{n}\right\rVert_\infty>\frac\lambda2\right)
\leq2p\exp\left(-\frac{n\lambda^2}{8\sigma^2}\right)
=2p^{-(A^2/8-1)}.
$$
On the complementary score event, the standard <Basic inequality for the Lasso>, cone argument, and compatibility oracle inequality give, for $S=\operatorname{supp}(\beta^0)$,
$$
\frac1n\lVert X(\widehat\beta-\beta^0)\rVert_2^2
+\lambda\lVert\widehat\beta-\beta^0\rVert_1
\leq\frac{16\lambda^2s}{\phi_{\widehat\Sigma}^2(S)}.
$$
Using part b and $\lambda^2=A^2\sigma^2\log p/n$ proves
$$
\boxed{
\frac1n\lVert X(\widehat\beta-\beta^0)\rVert_2^2
+\lambda\lVert\widehat\beta-\beta^0\rVert_1
\leq\frac{32A^2\sigma^2\log p}{\eta}\frac{s}{n}}
$$
with the required probability.
Back to article page
