Proximal gradient method

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}={\mathrm{prox}}_{\alpha h}(x_r-\alpha \nabla g(x_r))$. A standard choice $0<\alpha \le 1/L$ gives objective error $O(1/r)$ in the general convex case.

This basic forward-backward update is one of the proximal gradient methods for learning.

For a jointly smooth convex function $f(x,y)$, update $y$ implicitly by its proximal minimization at fixed $x$, then update $x$ explicitly with the gradient at the mixed point $(x,y^{+})$. The combined map is $(\tau L/2)$-averaged for $0<\tau L<2$, as follows by applying cocoercivity at two mixed points. Its fixed points are precisely the minimizers. If a minimizer exists, averaged iteration proves convergence.

For $f(x,y)=h(x,y)+\varphi (y)$, where $h$ is convex with an $L_h$-Lipschitz gradient and $\varphi$ is convex, use a proximal $y$-step for the full section and an explicit $x$-step for $h$. Monotonicity of the two selected subgradients of $\varphi$ combines with cocoercivity of $\nabla h$ to make the full update firmly nonexpansive for $0<\tau L_h\le 1$. Existence of a minimizer then gives convergence, even though the full objective is not smooth.

For two mixed points with difference $(p,q)$ and gradient difference $(a,b)$, the input difference is $(p,q+\tau b)$ and the output difference is $(p-\tau a,q)$. Their squared-norm difference is $-2\tau (⟨p,a⟩+⟨q,b⟩)+{\tau }^2(\Vert a{\Vert }^2-\Vert b{\Vert }^2)$. This exact identity is a reusable way to prove averagedness without assuming the two block maps are individually nonexpansive.

The iterative soft-thresholding algorithm applies the proximal gradient method to $\Vert x{\Vert }_1+\frac{1}{2}\Vert Ax-y{\Vert }_2^2$:Here $S_{\tau }$ is coordinatewise soft thresholding. The objective is convex and coercive, so iterates converge to a minimizer in finite dimensions; uniqueness requires additional hypotheses.