Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 205 / 3

With the normalization used here, the Lasso estimator minimizesOptimality at $\hat{\beta }$ relative to the feasible point ${\beta }^0$ givesThe columns of $X$ are centered, so $X^{T}1=0$ and the centered noise produces the same score function as $\epsilon$. Expanding the two squared norms and cancelling the noise norm yields the standard Basic inequality for the LassoThus the displayed inequality in the question has a factor-of-two typo: its left side should be $\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2/(2n)$, or both terms on its right should be doubled. No scaling of the usual squared-error Lasso objective produces the three displayed coefficients simultaneously. Parts b and d explicitly ask us to use the stated inequality, so their requested constants follow from that stated version.

Write $\delta =\hat{\beta }-{\beta }^0$. On $\Omega$, Hölder's inequality givesSince ${\beta }_N^0=0$, the triangle inequality givesSubstitution in the Basic inequality for the Lasso, followed by discarding the nonnegative prediction-error term, yieldsTherefore $\Vert {\hat{\beta }}_N-{\beta }_N^0{\Vert }_1\le 3\Vert {\hat{\beta }}_S-{\beta }_S^0{\Vert }_1$, the Lasso cone condition.

For each column $X_j$, the normalized score isThe errors are independent Rademacher random variables, and $\Vert X_j{\Vert }_2^2=n$. The Hoeffding lemma therefore makes $W_j$ a sub-Gaussian random variable with variance proxy $1/n$, soThe union bound with $t=\lambda /2$ givesFor $\lambda =A\sqrt{\log p/n}$ this becomesIn particular, if $A>\sqrt{8}$, the lower bound tends to one as $p\to \infty$.

Part b places $\delta =\hat{\beta }-{\beta }^0$ in the Lasso cone condition. Keeping the prediction-error term in the same argument giveswhere the second step is the Cauchy-Schwarz inequality. The restricted eigenvalue condition givesfor nonzero $\delta$ in this cone. Division by $\Vert \delta {\Vert }_2$ provesThe result is immediate when $\delta =0$.