Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 31J / f / Solution

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.