Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 31J (Mathematics of Machine Learning)

A set $C\subseteq {\mathbb{R}}^d$ is convex when every line segment between two of its points remains in the set: for every $x,y\in C$ and $0\le t\le 1$,

A function $f:C\to \mathbb{R}$ is strictly convex when, for distinct $x,y\in C$ and $0<t<1$,

Suppose distinct points $x$ and $y$ were both minimizers, with minimum value $m$. Since $C$ is a convex set, their midpoint belongs to $C$, while strict convexity givesa contradiction. Thus any minimizer is unique, which is the uniqueness of a minimizer of a strictly convex function.

For $x\in {\mathbb{R}}^d$, the euclidean projection onto a convex set $C$ isThe squared distance $z\mapsto \Vert x-z{\Vert }_2^2$ is a strictly convex function. Its restriction to the convex set $C$ can therefore have at most one minimizer by part (b). Closedness, together with finite dimensionality, supplies existence, although existence was not required to be proved.

Assume $\pi \in C$ andfor every $z\in C$. Expanding the squared euclidean distance givesHence $\pi$ minimizes the distance from $x$ over $C$, so $\pi ={\pi }_C(x)$. This proves the sufficient direction of the variational characterization of convex projection.

The set $C$ is the second-order cone. PutWhen $\rho \ge |t|$ and $\rho >0$, one has $0\le \alpha \le 1$, and the proposed pointlies on the boundary of $C$ because $\Vert \alpha u{\Vert }_2=\alpha \rho$.

Set $\delta =(\rho -t)/2\ge 0$. Sincefor any $(v,s)\in C$ we obtainwhere the first inequality is the Cauchy-Schwarz inequality and the second uses $\Vert v{\Vert }_2\le s$. Part (d) therefore giveswhenever $\Vert u{\Vert }_2\ge |t|$ and $u\ne 0$. At $(u,t)=(0,0)$ the projection is plainly $(0,0)$, consistent with the limiting formula.

If $\rho \le -t$, then for every $(v,s)\in C$,Applying part (d) with $\pi =0$ givesTogether with the trivial case $\rho \le t$, this is the full projection onto the second-order cone.

Using the harmless normalization $1/(2n)$, the squared-loss empirical risk for linear prediction iswith explicit gradientStarting from any ${\beta }_0\in C$, projected gradient descent with step sizes ${\eta }_k>0$ is

For a fully explicit update, write ${\tilde{\beta }}_{k+1}=(u_k,t_k)$ and ${\rho }_k=\Vert u_k{\Vert }_2$. The projection from part (e) isEvery iterate therefore lies in the prescribed hypothesis class, and any convergent run under the standard convex-optimization step-size conditions targets its empirical-risk minimizer.