Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 339 / 2 / e / Solution

SetThe gradient has Lipschitz continuity with constantwhere the norm is the spectral norm. The proximal gradient method is thereforeFor $\lambda >0$, part d makes the second step explicit:where $C$ is the capped simplex; when $\lambda =0$, this proximal step is the identity.

A standard fixed choice is $0<\alpha \le 1/L$; the wider interval $0<\alpha <2/L$ also gives convergence under the usual forward-backward conditions. For a general convex objective, the function-value error is $O(1/r)$. If $A$ has full column rank, the quadratic term is strongly convex and an appropriate fixed step gives a linear convergence rate.