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.

Fix $x$ with nonempty subdifferential $\partial h(x)$ for a convex function $h$. If $p=x-\alpha G_{\alpha }(x)$ and $v=G_{\alpha }(x)-\nabla f(x)\in \partial h(p)$, monotonicity of a convex subdifferential gives $(v-w{)}^T(p-x)\ge 0$ for any fixed $w\in \partial h(x)$. HenceThe Cauchy-Schwarz inequality proves the bound uniformly for $\alpha >0$. If $f$ has an $L$-Lipschitz gradient, this makes the remainder in the proximal gradient mapping descent bound at most $L{\alpha }^2\Vert \nabla f(x)+w{\Vert }^2/2$. Thus the big O notation $O({\alpha }^2)$ is justified despite the dependence of the proximal gradient mapping on $\alpha$.

Target: convex-optimization.bigb, under Coordinate descent.

For $\varphi =f+h$, with $f$ a convex function having an $L$-Lipschitz gradient and $h$ a proper convex function with a well-defined proximal operator, the proximal gradient method with step size $1/L$ satisfies the displayed bound whenever a global minimizer $x^{\ast }$ exists. The one-step subgradient inequality and descent lemma giveThe objective function values are nonincreasing. A telescoping sum over $j=0,\dots ,k-1$, followed by comparison of the last error with the arithmetic mean of the errors, proves the result. The bound controls the last objective function error without requiring a strongly convex function or a unique minimizer.

Target: convex-optimization.bigb, under Proximal gradient method.

For a convex function $h$ with a well-defined proximal operator, and a differentiable function $f$, the proximal gradient mapping is the displacement of one proximal gradient method update divided by its positive step size $\alpha$. Writing $p=x-\alpha G_{\alpha }(x)$, the subgradient optimality condition gives $G_{\alpha }(x)-\nabla f(x)\in \partial h(p)$. For convex functions $f,h$, its zeros are precisely the global minimizers of $f+h$, by the subgradient optimality condition and subdifferential sum rule. When $h=0$, it is the ordinary gradient.

Target: convex-optimization.bigb, under Proximal gradient method.

Let $f:{\mathbb{R}}^p\times {\mathbb{R}}^q\to \mathbb{R}$ be a differentiable convex function whose full gradient is $L$-Lipschitz continuous, with $L>0$. The alternating update first solves the implicit $y$ step and then the explicit $x$ step:The implicit step is the proximal operator of $\tau f(x,\cdot )$, so it exists uniquely. The gradient bound must control the full joint variable; smoothness alone supplies no global constant $L$.

For two updates, let $(p,q)$ be the difference of their mixed points $(x,y^{+})$ and $(a,b)$ the corresponding full gradient difference. The input and output differences are $(p,q+\tau b)$ and $(p-\tau a,q)$. The mixed-point norm identity for alternating updates and Baillon–Haddad theorem giveHence $T$ is a $(\tau L/2)$-averaged operator for $0<\tau L<2$. Its fixed points have both block gradients zero and are exactly the global minimizers of $f$. If a minimizer exists, Browder convergence theorem for averaged operators gives norm convergence of iteration in the stated finite-dimensional setting.

Let $h:{\mathbb{R}}^p\times {\mathbb{R}}^q\to \mathbb{R}$ be convex with an $L_h$-Lipschitz gradient, $L_h>0$, and let $\varphi :{\mathbb{R}}^q\to \mathbb{R}\cup \{+\infty \}$ be a proper lower semicontinuous convex function. For $f(x,y)=h(x,y)+\varphi (y)$, takeThe proper closed convex assumption on $\varphi$ ensures that the implicit section has a well-defined proximal operator.

For two mixed points with difference $(p,q)$, write $(a,b)$ for the gradient difference of $h$ and $w$ for the difference of the selected subgradients of $\varphi$. Inputs differ by $(p,q+\tau (b+w))$ and outputs by $(p-\tau a,q)$. Monotonicity of a convex subdifferential gives $⟨q,w⟩\ge 0$, while cocoercivity gives $⟨p,a⟩+⟨q,b⟩\ge L_h^{-1}(\Vert a{\Vert }^2+\Vert b{\Vert }^2)$. Expanding these squared norms provesfor $0<\tau L_h\le 1$. Thus the combined update is firmly nonexpansive. Its fixed points are the minimizers of $h+\varphi$; if one exists, the Browder convergence theorem for averaged operators gives norm convergence in finite dimensions.

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.