Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 210 / 3 / e / Solution

Let $B_{\delta }=\sqrt{\log (2m)}+\sqrt{\log (1/\delta )}$. The columns of $D^{†}/L$ have Euclidean norm at most one. Under the usual sub-Gaussian random vector convention, 3(d) justifies the tuning choice $\lambda =2\sqrt{2}L{B}_{\delta }/n$, which is independent of ${\theta }^{\ast }$. Also $\Vert {\Pi }_{1}z{\Vert }_2=|⟨z,1/\sqrt{n}⟩|$, so the Chernoff bound gives $\Vert {\Pi }_{1}z{\Vert }_2^2\le c_{\delta }=2\log (2/\delta )$ with probability at least $1-\delta$.

On the intersection of these events, of probability at least $1-2\delta$, set $a=\Vert h{\Vert }_2/\sqrt{n}$ and $b=\Vert {\Pi }_{1}z{\Vert }_2/\sqrt{n}$. The weighted Young inequality gives $2ab\le t^2{a}^2+b^2/t^2$ for $0<t<1$. Applying it to 3(c) and rearranging yields the rigorous boundIf the coefficient-one concentration statement in 3(d) is taken as an extra hypothesis, instead choose $\lambda =2L{B}_{\delta }/n$; the identical argument gives precisely the printed coefficient $4$ in the first term. Thus the deterministic argument and its risk rate are sound; its concentration constants depend on correcting or strengthening 3(d).