Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 205 / 2

For $s=|S|>0$, the compatibility constant in the convention used here is

Let $D$ be the block-diagonal part of $\hat{\Sigma }=n^{-1}{X}^{T}X$. The within-block eigenvalue assumption gives ${\delta }^{T}D\delta \ge \eta \Vert \delta {\Vert }_2^2$. On the compatibility cone with $\Vert {\delta }_S{\Vert }_1=1$,The off-block assumption therefore givesIt follows that ${\delta }^T\hat{\Sigma }\delta \ge \eta /(2s)$, and hence

Because $\Vert X_j{\Vert }_2=\sqrt{n}$, each coordinate of $X^T\epsilon /n$ is $N(0,{\sigma }^2/n)$. The Gaussian tail bound and a union bound giveOn the complementary score event, the standard Basic inequality for the Lasso, cone argument, and compatibility oracle inequality give, for $S=\mathrm{supp}({\beta }^0)$,Using part b and ${\lambda }^2=A^2{\sigma }^2\log p/n$ proveswith the required probability.