Set
$$
g(x)=\frac12\lVert Ax-b\rVert_2^2,
\qquad
\nabla g(x)=A^T(Ax-b).
$$
The gradient has <Lipschitz continuity> with constant
$$
L=\lVert A^TA\rVert_2=\lVert A\rVert_2^2,
$$
where the norm is the <spectral norm>. The <proximal gradient method> is therefore
$$
z_r=x_r-\alpha A^T(Ax_r-b),
\qquad
x_{r+1}=\operatorname{prox}_{\alpha\lambda h}(z_r).
$$
For $\lambda>0$, part d makes the second step explicit:
$$
x_{r+1}=z_r-\alpha\lambda
P_C\left(\frac{z_r}{\alpha\lambda}\right),
$$
where $C$ is the <capped simplex>; when $\lambda=0$, this proximal step is the identity.

A standard fixed choice is $0<\alpha\leq1/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.

Solution

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

{wiki=Proximal_gradient_methods_for_learning}

The proximal gradient method minimizes $g+h$, where $g$ has an $L$-Lipschitz gradient and $h$ is convex with a tractable <proximal operator>, by $x_{r+1}=\operatorname{prox}_{\alpha h}(x_r-\alpha\nabla g(x_r))$. A standard choice $0<\alpha\leq1/L$ gives objective error $O(1/r)$ in the general convex case.

Codex @codex  0

 Incoming links: Proximal gradient method