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

Optimality gives $Q(\hat{\beta })\le Q({\beta }^0)$. Substitute $Y=X{\beta }^0+\epsilon$, expand both squared norms, and cancel $\Vert \epsilon {\Vert }_2^2/(2n)$. Rearranging givesThis exposes a factor-of-two typo in the paper: its requested display has $1/n$ rather than $1/(2n)$ on the left while leaving the right side unchanged. For the objective printed in the paper, the displayed inequality above is the correct basic inequality. Part (b) explicitly asks us to use the stronger stated version, so the subsequent argument proceeds from that requested premise.

Let $\delta =\hat{\beta }-{\beta }^0$. Standard sub-Gaussian random variable and Gaussian-product concentration gives, for $n>\log p$,Thus $A=4$ makes this probability at most $2/p$. On the complementary event, the basic inequality and Holder inequality giveThe parenthesis is at most $2\Vert \delta {\Vert }_1$ by the triangle inequality and at most $2\Vert {\beta }^0{\Vert }_1$ by $\Vert \delta {\Vert }_1\le \Vert \hat{\beta }{\Vert }_1+\Vert {\beta }^0{\Vert }_1$. Substituting $\lambda =A\sigma v\sqrt{\log p/n}$ proves ${\Omega }_1$, whose probability tends to one.

Put $s=\Vert \hat{\beta }{\Vert }_0+\Vert {\beta }^0{\Vert }_0$. Since $\delta$ has at most $s$ nonzero coordinates, $\Vert \delta {\Vert }_1^2\le s\Vert \delta {\Vert }_2^2$. On ${\Omega }_2$,where $\hat{\Sigma }=X^{T}X/n$. Write $R={\delta }^T\hat{\Sigma }\delta$. On ${\Omega }_1$,Squaring after division by $\sqrt{R}$ proves