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

For a convex function $f:{\mathbb{R}}^d\to \mathbb{R}$, its subdifferential at $x$ isIts elements are the subgradients of $f$ at $x$.

Only the $k$th block can have nonzero subgradient coordinates. If ${\beta }^{(k)}\ne 0$, the Cauchy-Schwarz inequality shows that the unique supporting vector is ${\beta }^{(k)}/\Vert {\beta }^{(k)}{\Vert }_2$. At zero, the defining inequality is $\Vert h{\Vert }_2\ge u^{T}h$ for every block vector $h$, which is equivalent to $\Vert u{\Vert }_2\le 1$. Thus

The differentiable loss has gradient $X^T(X\beta -Y)/n$. The subdifferential sum rule and part (b) givewhere blockwise

Suppose ${\hat{\beta }}_1$ and ${\hat{\beta }}_2$ minimize $Q$. Their midpoint is also a minimizer because $Q$ is a convex function. The group penalty is convex, while the squared Euclidean norm is strictly convex in the fitted value. If $X{\hat{\beta }}_1\ne X{\hat{\beta }}_2$, strict convexity would make the midpoint objective strictly smaller than the minimum. Hence $X{\hat{\beta }}_1=X{\hat{\beta }}_2$, so the fitted values are unique.

Part (d) makes the residual and therefore $\hat{\nu }=X^T(Y-X\hat{\beta })$ unique, so $E$ is unique. The Karush-Kuhn-Tucker conditions from part (c) imply that every nonzero block satisfies $\Vert {\hat{\nu }}^{(k)}{\Vert }_2=n\lambda \sqrt{m}$. Hence ${\hat{\beta }}^{(k)}=0$ for $k\notin E$.

Any two minimizers have the same fitted value and vanish outside $E$. Their difference $h$ is therefore supported on $E$ and satisfies $\tilde{X}{h}_E=0$. If $\tilde{X}$ has full column rank, then $h_E=0$, proving uniqueness of $\hat{\beta }$.