= Solution
A sufficient set of assumptions is: the columns of the deterministic designs have Euclidean norm at most $\sqrt n$; the true support has size $s$; the <compatibility constant> on that support is bounded below uniformly; $\log p=o(n)$; and $s\log p/\sqrt n\to0$. Choose $A$ large enough that the Gaussian score event
$$
\left\lVert X^T\varepsilon/n\right\rVert_\infty\leq\lambda/2
$$
has probability tending to one. The standard compatibility oracle inequality then gives
$$
\lVert\widehat\beta-\beta^0\rVert_1
=O_p\left(s\sqrt{\frac{\log p}{n}}\right).
$$
Part b consequently yields
$$
\lVert\Delta\rVert_\infty
=O_p\left(\frac{s\log p}{\sqrt n}\right).
$$
Equivalently, for a sufficiently large constant $c$,
$$
\mathbb P\left(\lVert\Delta\rVert_\infty>\frac{cs\log p}{\sqrt n}\right)\longrightarrow0.
$$
Back to article page
