Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 205 / 1 / Solution

With the usual objectivethe Karush-Kuhn-Tucker conditions for the Lasso areComparing the objective at ${\hat{\beta }}_{\lambda }$ and ${\beta }^0$, expanding the square, and cancelling the noise norm gives exactly

Choose $\lambda =A\sigma \sqrt{\log p/n}$. Since every column has norm $\sqrt{n}$, each $X_j^T\epsilon /n$ is sub-Gaussian with parameter $\sigma /\sqrt{n}$. A union bound givesOn the complementary event, Holder inequality and the triangle inequality bound the preceding right-hand side bywhich proves the stated prediction bound.

For the Dantzig selector, use the constraint $n^{-1}\Vert X^T(Y-X\beta ){\Vert }_{\infty }\le \lambda$. The Lasso KKT conditions make ${\hat{\beta }}_{\lambda }$ feasible, so a Dantzig minimizer $\tilde{\beta }$ has no larger ${\ell }^1$ norm. If $\tilde{\beta }$ were not the Lasso solution, uniqueness from invertibility of $X^{T}X$ would imply that some active coordinate $j$ has strict signed KKT slack. For small $\eta >0$, setOnly score coordinate $j$ changes, toward its feasible boundary, so ${\beta }_{\eta }$ remains feasible. For small $\eta$, signs on the active coordinates do not change, andby strict diagonal dominance. This contradicts Dantzig optimality, so the two estimators coincide.