= Solution
Let $\delta=\widehat\beta-\beta^0$. Standard <sub-Gaussian random variable> and Gaussian-product concentration gives, for $n>\log p$,
$$
\mathbb P\left(\left\lVert\frac1nX^T\varepsilon\right\rVert_\infty
>A\sigma v\sqrt{\frac{\log p}{n}}\right)
\leq2p\exp(-A^2\log p/8).
$$
Thus $A=4$ makes this probability at most $2/p$. On the complementary event, the basic inequality and <Holder inequality> give
$$
\frac1n\lVert X\delta\rVert_2^2
\leq\lambda\bigl(\lVert\delta\rVert_1+
\lVert\beta^0\rVert_1-\lVert\widehat\beta\rVert_1\bigr).
$$
The parenthesis is at most $2\lVert\delta\rVert_1$ by the triangle inequality and at most $2\lVert\beta^0\rVert_1$ by $\lVert\delta\rVert_1\leq\lVert\widehat\beta\rVert_1+\lVert\beta^0\rVert_1$. Substituting $\lambda=A\sigma v\sqrt{\log p/n}$ proves $\Omega_1$, whose probability tends to one.
Back to article page
