The Proximal Operator, Moreau Envelope, and Proximal-Gradient Method

Intuition Beginner

A plain gradient step asks one question: which way is downhill, and how far should I walk? It works when the landscape is smooth. But many real cost functions are part smooth and part sharp — a smooth data-fitting bowl plus a sharp penalty that pushes answers toward zero. On the sharp part there is no single downhill direction, so a pure gradient step stalls. We need a move that respects both pieces at once.

The proximal operator is that move. Instead of taking a fixed step and hoping, you solve a small, friendly problem at every iteration: "find the point that makes the sharp penalty small while staying close to where I am now." The phrase "staying close" is a spring that pulls you back toward your current spot; the strength of the spring is the step size. A strong spring barely moves you; a weak spring lets the penalty drag you far. The answer to that small problem is the proximal step.

Two everyday pictures make it concrete. If the sharp penalty is "you must land inside this fenced field," then the friendly problem is "find the nearest point inside the fence" — that is just projection, walking to the closest legal spot. If the penalty is "keep your answer small, and prefer exact zeros," the friendly problem has a clean rule: shrink every number toward zero by a fixed amount, and snap anything small all the way to zero. That shrink-and-snap rule is called soft thresholding, and it is why these methods produce sparse, mostly-zero answers.

The full method alternates. Take an ordinary gradient step on the smooth part — a forward step. Then apply the proximal step for the sharp part — a backward step that cleans up. Repeat. Because the smooth part is genuinely smooth, this forward-backward rhythm makes steady progress, faster than treating the whole thing as one big sharp problem.

Visual Beginner

Picture one iteration as two moves. First a gradient step slides you downhill on the smooth bowl. Then the proximal step pulls you toward the point that balances the penalty against staying close, landing you on a cleaner spot — often with some coordinates snapped exactly to zero.

   smooth part f            sharp part g (penalty)        one prox-grad step
   (a bowl)                 (a sharp V at 0)              forward then backward

      \    /                     \      /                  x_k
       \  /                       \    /                    |  gradient step (forward)
        \/                         \  /                     v
   gradient points                 \/                  x_k - t*grad f(x_k)
   straight downhill          no single                     |  prox of g (backward)
                              downhill at 0                  v
                                                        x_{k+1}  (snapped toward 0)

sharp penalty g	the proximal step does
indicator of a set (must stay inside)	project onto the set: walk to the nearest legal point
the size penalty $\lambda |x{|}_1$	soft threshold: shrink each number toward 0 by $\lambda$, snap small ones to 0
nothing (g = 0)	leave the point where it is: prox is the identity

Worked example Beginner

We soft-threshold a single number. Take the penalty $g(x)=\lambda |x|$ with $\lambda =2$, and find the proximal step starting from $v=5$. The small friendly problem is: pick $x$ to make $2|x|+\frac{1}{2}(x-5{)}^2$ as small as possible.

Step 1. Guess the answer is positive. If $x>0$ the penalty is $2x$, so we minimise $2x+\frac{1}{2}(x-5{)}^2$. Its slope in $x$ is $2+(x-5)$. Setting the slope to zero gives $x-5=-2$, so $x=3$. Since $3>0$, the guess holds.

Step 2. Read the rule. The starting value $5$ got pulled down to $3$ — it shrank by exactly $\lambda =2$. That is the shrink rule: a positive number loses $\lambda$.

Step 3. Try a small starting value. Now start from $v=1$ with the same $\lambda =2$. Shrinking $1$ by $2$ would overshoot past zero. The honest answer is to stop at zero: the proximal step returns $x=0$. You can check that any positive $x$ makes $2x+\frac{1}{2}(x-1{)}^2$ larger than the value at $x=0$, which is $\frac{1}{2}$.

Step 4. State the full rule. Soft thresholding sends $v$ to $v-\lambda$ if $v>\lambda$, to $v+\lambda$ if $v<-\lambda$, and to $0$ if $|v|\le \lambda$. So $5\mapsto 3$, $1\mapsto 0$, and $-4\mapsto -2$.

What this tells us. The proximal step for the size penalty is not magic: it is shrink-toward-zero-and-snap. Small numbers become exactly zero, which is how these methods select a few important variables and discard the rest.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $f,g:{\mathbb{R}}^n\to (-\infty ,+\infty ]$ are proper closed (lower semicontinuous) convex, with $⟨\cdot ,\cdot ⟩$ the Euclidean inner product and $\Vert \cdot \Vert$ its norm. The subdifferential $\partial f$ and the Fermat rule $0\in \partial f(x^{\star })$ are as in 44.02.05.

Definition (proximal operator). For a proper closed convex $f$ and parameter $\lambda >0$, the proximal operator is the map

$${\mathrm{prox}}_{\lambda f}(v)=\arg \underset{x\in {\mathbb{R}}^n}{\min }\{f(x)+\frac{1}{2\lambda }\Vert x-v{\Vert }^2\}.$$

The objective is the sum of a convex function and a $\frac{1}{\lambda }$-strongly convex quadratic, hence $\frac{1}{\lambda }$-strongly convex; together with closedness and coercivity this makes the minimiser exist and be unique, so ${\mathrm{prox}}_{\lambda f}$ is a single-valued map ${\mathbb{R}}^n\to {\mathbb{R}}^n$ (first prox theorem) ^{[Beck, A. — First-Order Methods in Optimization (SIAM, 2017)]}. Writing ${\mathrm{prox}}_f:={\mathrm{prox}}_{1\cdot f}$, the general case is ${\mathrm{prox}}_{\lambda f}(v)=\arg {\min }_x\{\lambda f(x)+\frac{1}{2}\Vert x-v{\Vert }^2\}$.

Definition (Moreau envelope). The Moreau envelope (or Moreau-Yosida regularisation) of $f$ with parameter $\lambda >0$ is the value of that minimisation:

$$M_{\lambda f}(x)=\underset{u\in {\mathbb{R}}^n}{\min }\{f(u)+\frac{1}{2\lambda }\Vert u-x{\Vert }^2\}.$$

It is a finite, convex, continuously differentiable function with $M_{\lambda f}\le f$, the same minimisers and minimum value as $f$, and gradient

$$\nabla M_{\lambda f}(x)=\frac{1}{\lambda }(x-{\mathrm{prox}}_{\lambda f}(x)),$$

which is $\frac{1}{\lambda }$-Lipschitz. The envelope is thus a smooth surrogate for a possibly nonsmooth $f$, and a gradient step on $M_{\lambda f}$ is a proximal step on $f$.

Definition (resolvent / second prox theorem). The proximal operator is the resolvent of the maximal monotone operator $\partial f$:

$${\mathrm{prox}}_{\lambda f}=(I+\lambda \partial f{)}^{-1},\text{equivalently}u={\mathrm{prox}}_{\lambda f}(v)⟺\frac{v-u}{\lambda }\in \partial f(u).$$

Definition (firm nonexpansiveness). ${\mathrm{prox}}_{\lambda f}$ is firmly nonexpansive:

$$\Vert {\mathrm{prox}}_{\lambda f}(x)-{\mathrm{prox}}_{\lambda f}(y){\Vert }^2\le ⟨{\mathrm{prox}}_{\lambda f}(x)-{\mathrm{prox}}_{\lambda f}(y),x-y⟩,$$

which implies $1$-Lipschitz (nonexpansive) behaviour, $\Vert {\mathrm{prox}}_{\lambda f}(x)-{\mathrm{prox}}_{\lambda f}(y)\Vert \le \Vert x-y\Vert$.

Definition (composite problem and proximal-gradient method). Consider the composite objective

$$\underset{x\in {\mathbb{R}}^n}{\min }F(x):=f(x)+g(x),$$

with $f$ convex and $L$-smooth ($\nabla f$ is $L$-Lipschitz) and $g$ proper closed convex but possibly nonsmooth and "simple" (its prox is cheap). The proximal-gradient method (forward-backward splitting), with step $t\in (0,1/L]$, iterates

$$x_{k+1}={\mathrm{prox}}_{tg}(x_k-t\nabla f(x_k))=:T_t(x_k).$$

The forward (explicit) step $x_k-t\nabla f(x_k)$ uses the gradient of $f$; the backward (implicit) step ${\mathrm{prox}}_{tg}$ uses the resolvent of $\partial g$. Two limiting cases anchor the picture: $g=0$ gives ordinary gradient descent, and $f=0$ gives the proximal point method $x_{k+1}={\mathrm{prox}}_{tg}(x_k)$.

Counterexamples to common slips Intermediate+

• "The prox is a gradient step on $f$." It is a gradient step on the envelope $M_{\lambda f}$, not on $f$. For nonsmooth $f$ such as $|x|$, $f$ has no gradient at $0$, yet ${\mathrm{prox}}_{\lambda f}$ is perfectly defined (soft thresholding) and equals the resolvent $(I+\lambda \partial f{)}^{-1}$.

• "Any step size $t$ converges." The $O(1/k)$ rate needs $t\le 1/L$. With $g=0$ and $t>2/L$, plain gradient descent diverges on a quadratic; the proximal-gradient method inherits this restriction through the descent lemma, which uses $L$-smoothness of $f$.

• "${\mathrm{prox}}_{\lambda f}$ depends only on $f$, not $\lambda$." The parameter sets the spring strength: ${\mathrm{prox}}_{\lambda (\lambda \Vert \cdot {\Vert }_1)}$ soft-thresholds at level $\lambda$, and as $\lambda \to 0$ the prox tends to the identity, while as $\lambda \to \infty$ it tends to the minimiser of $f$.

Key theorem with proof Intermediate+

The composite theory rests on one estimate per step: the proximal-gradient map decreases a quadratic model of $F$ enough that the suboptimality telescopes to $O(1/k)$. The fixed-point equivalence first certifies that the limit is a minimiser.

Theorem (fixed points and the $O(1/k)$ rate). Let $F=f+g$ with $f$ convex and $L$-smooth and $g$ proper closed convex, and let $x^{\star }$ minimise $F$. Then:

(i) (Fixed-point characterisation.) For any $t>0$, $x^{\star }={\mathrm{prox}}_{tg}(x^{\star }-t\nabla f(x^{\star }))$ if and only if $0\in \nabla f(x^{\star })+\partial g(x^{\star })$, i.e. $x^{\star }$ minimises $F$.

(ii) (Sufficient decrease.) For $0<t\le 1/L$ and any $x$, writing $x^{+}=T_t(x)={\mathrm{prox}}_{tg}(x-t\nabla f(x))$, for every $y$,

$$F(x^{+})\le F(y)+\frac{1}{2t}(\Vert x-y{\Vert }^2-\Vert x^{+}-y{\Vert }^2).\text{\hspace{1em}(†)}$$

(iii) ($O(1/k)$ rate.) With $0<t\le 1/L$ and $R=\Vert x_0-x^{\star }\Vert$,

$$F(x_k)-F(x^{\star })\le \frac{\Vert x_0-x^{\star }{\Vert }^2}{2tk}\le \frac{L{R}^2}{2k}.$$

Proof. (i) By the second prox theorem, $u={\mathrm{prox}}_{tg}(v)$ iff $\frac{v-u}{t}\in \partial g(u)$. Put $v=x^{\star }-t\nabla f(x^{\star })$, $u=x^{\star }$: the fixed-point equation holds iff $\frac{(x^{\star }-t\nabla f(x^{\star }))-x^{\star }}{t}=-\nabla f(x^{\star })\in \partial g(x^{\star })$, i.e. $0\in \nabla f(x^{\star })+\partial g(x^{\star })$. Since $f$ is differentiable convex and $g$ convex, the sum rule 44.02.05 gives $\partial F=\nabla f+\partial g$, so this is exactly Fermat's rule $0\in \partial F(x^{\star })$, equivalent to $x^{\star }\in \arg \min F$.

(ii) Two facts combine. First, the descent lemma for an $L$-smooth convex $f$: for all $u,x$,

$$f(u)\le f(x)+⟨\nabla f(x),u-x⟩+\frac{L}{2}\Vert u-x{\Vert }^2.\text{\hspace{1em}(1)}$$

Second, the prox step minimises a regularised model. By the second prox theorem applied to $x^{+}={\mathrm{prox}}_{tg}(x-t\nabla f(x))$,

$$\frac{(x-t\nabla f(x))-x^{+}}{t}\in \partial g(x^{+}),\text{i.e.}\frac{x-x^{+}}{t}-\nabla f(x)\in \partial g(x^{+}).$$

Call this subgradient $\gamma :=\frac{x-x^{+}}{t}-\nabla f(x)\in \partial g(x^{+})$. The subgradient inequality for $g$ at $x^{+}$ gives, for every $y$,

$$g(y)\ge g(x^{+})+⟨\gamma ,y-x^{+}⟩.\text{\hspace{1em}(2)}$$

Now bound $F(x^{+})=f(x^{+})+g(x^{+})$. Using (1) with $u=x^{+}$ and $t\le 1/L$ so that $\frac{L}{2}\le \frac{1}{2t}$,

$$f(x^{+})\le f(x)+⟨\nabla f(x),x^{+}-x⟩+\frac{1}{2t}\Vert x^{+}-x{\Vert }^2.$$

From (2), $g(x^{+})\le g(y)-⟨\gamma ,y-x^{+}⟩=g(y)-⟨\frac{x-x^{+}}{t}-\nabla f(x),y-x^{+}⟩$. Adding, and using convexity of $f$ at $x$ in the form $f(x)+⟨\nabla f(x),y-x⟩\le f(y)$:

$$F(x^{+})\le f(y)+g(y)+⟨\nabla f(x),x^{+}-y⟩+\frac{1}{2t}\Vert x^{+}-x{\Vert }^2-⟨\frac{x-x^{+}}{t}-\nabla f(x),y-x^{+}⟩.$$

The $\nabla f(x)$ terms cancel: $⟨\nabla f(x),x^{+}-y⟩+⟨\nabla f(x),y-x^{+}⟩=0$. What remains is

$$F(x^{+})\le F(y)+\frac{1}{2t}\Vert x^{+}-x{\Vert }^2-\frac{1}{t}⟨x-x^{+},y-x^{+}⟩.$$

Apply the polarisation identity $\frac{1}{2t}\Vert x^{+}-x{\Vert }^2-\frac{1}{t}⟨x-x^{+},y-x^{+}⟩=\frac{1}{2t}(\Vert x-y{\Vert }^2-\Vert x^{+}-y{\Vert }^2)$, which holds because $\Vert x-y{\Vert }^2-\Vert x^{+}-y{\Vert }^2=\Vert x-x^{+}{\Vert }^2+2⟨x-x^{+},x^{+}-y⟩$. This is $(†)$.

(iii) Take $y=x^{\star }$ in $(†)$ at step $k$ ($x=x_k$, $x^{+}=x_{k+1}$):

$$F(x_{k+1})-F(x^{\star })\le \frac{1}{2t}(\Vert x_k-x^{\star }{\Vert }^2-\Vert x_{k+1}-x^{\star }{\Vert }^2).$$

The right side is nonnegative, so $\Vert x_{k+1}-x^{\star }\Vert \le \Vert x_k-x^{\star }\Vert$ (Fejér monotonicity). Summing $i=0,\dots ,k-1$ telescopes to ${\sum }_{i=0}^{k-1}(F(x_{i+1})-F(x^{\star }))\le \frac{1}{2t}\Vert x_0-x^{\star }{\Vert }^2$. Take $y=x_k$ in $(†)$ at step $k$ to see $F(x_{k+1})\le F(x_k)$, so the sequence $F(x_i)-F(x^{\star })$ is nonincreasing; hence $k(F(x_k)-F(x^{\star }))\le {\sum }_{i=1}^k(F(x_i)-F(x^{\star }))\le \frac{1}{2t}\Vert x_0-x^{\star }{\Vert }^2$. Dividing by $k$ and using $t\le 1/L$ gives the claim. $\square$

Bridge. The single estimate $(†)$ is the foundational reason the method converges, and it builds toward the accelerated and splitting methods of the rest of the chapter, where the same prox inequality is reused under a momentum extrapolation. This is exactly the composite analogue of the descent lemma behind smooth gradient descent: where that argument decreases $f$ by a full $\frac{L}{2}\Vert x^{+}-x{\Vert }^2$, here the prox step folds the nonsmooth $g$ into the same quadratic comparison through its subgradient, so the proof generalises gradient descent to $f+g$ with no loss of rate. The $O(1/k)$ bound is dual to the subgradient method's $O(1/\sqrt{k})$ of 44.06.01: putting these together, the central insight is that splitting off the smooth part and treating only $g$ by its prox escapes the nonsmooth black-box lower bound, and the fixed-point equation $0\in \nabla f+\partial g$ appears again in FISTA 44.06.03 and ADMM 44.06.04 as the optimality condition those methods solve.

Exercises Intermediate+

Advanced results Master

The proximal-gradient method is $x_{k+1}={\mathrm{prox}}_{tg}(x_k-t\nabla f(x_k))$, and the results below sharpen its rate under strong convexity, fix the prox calculus that makes the backward step computable, and place the iteration inside the operator-theoretic frame from which acceleration and splitting descend.

Theorem 1 (linear convergence under strong convexity). If in addition $f$ is $\mu$-strongly convex, then $F$ is $\mu$-strongly convex and the proximal-gradient map $T_t$ with $t=1/L$ is a contraction in the Euclidean norm: $\Vert T_t(x)-T_t(y)\Vert \le (1-\mu /L)\Vert x-y\Vert$, where $\kappa =L/\mu$ is the condition number. Consequently $\Vert x_k-x^{\star }\Vert \le (1-1/\kappa {)}^k\Vert x_0-x^{\star }\Vert$ and $F(x_k)-F^{\star }\le (1-1/\kappa {)}^{2k}(F(x_0)-F^{\star })$, a linear (geometric) rate replacing the sublinear $O(1/k)$ ^{[Beck, A. — First-Order Methods in Optimization (SIAM, 2017)]}. The contraction factor is exactly that of gradient descent on a smooth strongly convex function; the prox of $g$ is firmly nonexpansive and so does not degrade it.

Theorem 2 (Moreau envelope as a smoothing, and the proximal point method). The envelope $M_{\lambda f}$ is convex, finite, $C^1$ with $\frac{1}{\lambda }$-Lipschitz gradient $\nabla M_{\lambda f}(x)=\frac{1}{\lambda }(x-{\mathrm{prox}}_{\lambda f}(x))$, satisfies $\inf M_{\lambda f}=\inf f$ with identical minimiser set, and increases to $f$ pointwise as $\lambda \downarrow 0$. Gradient descent on $M_{\lambda f}$ with step $\lambda$ is precisely the proximal point algorithm $x_{k+1}={\mathrm{prox}}_{\lambda f}(x_k)$, the case $f\equiv 0$ of forward-backward applied to the single function $f$; it converges for any $\lambda >0$ because ${\mathrm{prox}}_{\lambda f}$ is firmly nonexpansive with fixed-point set $\arg \min f$ ^{[Parikh, N. & Boyd, S. — Proximal Algorithms (2014)]}. The envelope is the bridge: it turns a nonsmooth problem into a smooth one whose gradient steps are implicit (backward) steps on the original.

Theorem 3 (prox calculus). The proximal operator obeys a calculus making composite models tractable. Separable sum: ${\mathrm{prox}}_{\lambda g}$ acts coordinatewise for $g(x)={\sum }_i{g}_i(x_i)$ (Exercise 4). Affine precomposition with a tight frame: if $A{A}^{\top }=\frac{1}{\nu }I$ then ${\mathrm{prox}}_{g\circ A}(v)=v+\nu A^{\top }({\mathrm{prox}}_{g/\nu }(Av)-Av)$. Scaling and translation: ${\mathrm{prox}}_{g(\cdot -b)}(v)=b+{\mathrm{prox}}_g(v-b)$ and ${\mathrm{prox}}_{g(\rho \cdot )}$ reduces to ${\mathrm{prox}}_g$ by rescaling. Moreau decomposition (extended): $v={\mathrm{prox}}_{\lambda f}(v)+\lambda {\mathrm{prox}}_{f^{\ast }/\lambda }(v/\lambda )$ for $\lambda >0$, generalising Exercise 7 ^{[Beck, A. — First-Order Methods in Optimization (SIAM, 2017)]}. The decomposition recovers the orthogonal-projection identity $v=P_C(v)+P_{C^{\circ }}(v)$ onto a closed convex cone $C$ and its polar $C^{\circ }$ as the special case $f={\iota }_C$, $f^{\ast }={\iota }_{C^{\circ }}$.

Theorem 4 (acceleration: the FISTA rate). Inserting a Nesterov momentum extrapolation before the prox step — $y_k=x_k+\frac{t_{k-1}-1}{t_k}(x_k-x_{k-1})$ with $t_k=\frac{1+\sqrt{1+4t_{k-1}^2}}{2}$, then $x_{k+1}={\mathrm{prox}}_{tg}(y_k-t\nabla f(y_k))$ — yields the fast iterative shrinkage-thresholding algorithm with $F(x_k)-F^{\star }\le \frac{2L\Vert x_0-x^{\star }{\Vert }^2}{(k+1{)}^2}=O(1/k^2)$ ^{[Beck, A. — First-Order Methods in Optimization (SIAM, 2017)]}. This matches the $\Omega (1/k^2)$ lower bound for first-order methods on the $L$-smooth class, so acceleration is optimal there; the backward step and the sufficient-decrease lemma $(†)$ are reused unchanged, only the point at which the gradient is evaluated moves to the extrapolated $y_k$. The detailed estimate-sequence proof is the subject of 44.06.03.

Theorem 5 (forward-backward splitting as a resolvent iteration). Writing the optimality condition $0\in \nabla f(x^{\star })+\partial g(x^{\star })$ as $0\in (A+B)(x^{\star })$ with $A=\nabla f$ cocoercive and $B=\partial g$ maximal monotone, the proximal-gradient step is the forward-backward operator $x_{k+1}=(I+tB{)}^{-1}(I-tA)(x_k)=J_{tB}(I-tA)(x_k)$, where $J_{tB}=(I+tB{)}^{-1}={\mathrm{prox}}_{tg}$ is the resolvent of $B$ ^{[Combettes, P. L. & Wajs, V. R. — Signal recovery by proximal forward-backward splitting]}. Convergence of the iterates to a zero of $A+B$ holds for $t\in (0,2\beta )$ where $\beta$ is the cocoercivity constant of $A$ (here $\beta =1/L$), via averaged-operator / Krasnoselskii-Mann fixed-point theory. This operator viewpoint is the one ADMM 44.06.04 and Douglas-Rachford splitting generalise to sums of two arbitrary nonsmooth prox-friendly terms.

Synthesis. The proximal operator is exactly the resolvent $(I+\lambda \partial f{)}^{-1}$ of the maximal monotone subdifferential, and this single identification is the foundational reason the whole apparatus coheres: the second prox theorem $v-u\in \lambda \partial f(u)$ generalises the smooth gradient step to a nonsmooth implicit step, the Moreau envelope is dual to it — a smooth function whose gradient is the prox residual — and firm nonexpansiveness is exactly what makes both the proximal point and forward-backward iterations converge. The central insight is that splitting $F=f+g$ and treating $g$ by its prox rather than a subgradient escapes the $\Omega (1/\sqrt{k})$ black-box barrier of 44.06.01, buying $O(1/k)$ from the descent lemma $(†)$ and, with momentum, the optimal $O(1/k^2)$; this is exactly why the method dominates the subgradient baseline on composite problems. Putting these together, the Moreau decomposition ${\mathrm{prox}}_f+{\mathrm{prox}}_{f^{\ast }}=I$ is subgradient inversion $\partial f^{\ast }=(\partial f{)}^{-1}$ from 44.02.05 read at the resolvent level, tying the prox calculus to the conjugacy of 44.02.03, and the bridge from this unit to acceleration 44.06.03 and to ADMM 44.06.04 is precisely the operator identity $T_t=J_{tB}(I-tA)$, which those methods extend from one prox to a coordinated pair.

Full proof set Master

Proposition 1 (first prox theorem: existence and uniqueness). For proper closed convex $f$ and $\lambda >0$, ${\mathrm{prox}}_{\lambda f}(v)$ exists and is unique for every $v$.

Proof. The objective $\phi (x)=f(x)+\frac{1}{2\lambda }\Vert x-v{\Vert }^2$ is the sum of a proper closed convex $f$ and a $\frac{1}{\lambda }$-strongly convex closed quadratic, hence proper closed and $\frac{1}{\lambda }$-strongly convex. Strong convexity gives coercivity ($\phi (x)\to +\infty$ as $\Vert x\Vert \to \infty$): for a fixed subgradient $s\in \partial f(x_0)$ at any $x_0\in \mathrm{dom}f$, convexity gives $f(x)\ge f(x_0)+⟨s,x-x_0⟩$, so $\phi (x)\ge \frac{1}{2\lambda }\Vert x-v{\Vert }^2+⟨s,x⟩+\text{const}$, which is coercive. A proper closed coercive function on ${\mathbb{R}}^n$ attains its infimum (Weierstrass on a sublevel set, which is compact by closedness and coercivity), and a strongly convex function has at most one minimiser, since if $x_1\ne x_2$ both minimise, the midpoint $\bar{x}$ satisfies $\phi (\bar{x})\le \frac{1}{2}(\phi (x_1)+\phi (x_2))-\frac{1}{8\lambda }\Vert x_1-x_2{\Vert }^2<\inf \phi$, a contradiction. $\square$

Proposition 2 (second prox theorem: the resolvent characterisation). $u={\mathrm{prox}}_{\lambda f}(v)⟺\frac{v-u}{\lambda }\in \partial f(u)⟺{\mathrm{prox}}_{\lambda f}=(I+\lambda \partial f{)}^{-1}$.

Proof. By Proposition 1, $u={\mathrm{prox}}_{\lambda f}(v)$ is the unique minimiser of $\phi (x)=f(x)+\frac{1}{2\lambda }\Vert x-v{\Vert }^2$. By Fermat's rule 44.02.05 and the sum rule (the quadratic term is differentiable with gradient $\frac{1}{\lambda }(x-v)$, so its subdifferential is a singleton and the sum rule applies without a qualification), $u$ minimises $\phi$ iff $0\in \partial f(u)+\frac{1}{\lambda }(u-v)$, i.e. $\frac{v-u}{\lambda }\in \partial f(u)$. Rearranged, $v-u\in \lambda \partial f(u)$, i.e. $v\in u+\lambda \partial f(u)=(I+\lambda \partial f)(u)$, so $u=(I+\lambda \partial f{)}^{-1}(v)$; single-valuedness of the inverse is Proposition 1. $\square$

Proposition 3 (firm nonexpansiveness). For proper closed convex $f$ and $\lambda >0$, $\Vert {\mathrm{prox}}_{\lambda f}(x)-{\mathrm{prox}}_{\lambda f}(y){\Vert }^2\le ⟨{\mathrm{prox}}_{\lambda f}(x)-{\mathrm{prox}}_{\lambda f}(y),x-y⟩$; in particular ${\mathrm{prox}}_{\lambda f}$ is nonexpansive.

Proof. Write $p={\mathrm{prox}}_{\lambda f}(x)$, $q={\mathrm{prox}}_{\lambda f}(y)$. By Proposition 2, $\frac{x-p}{\lambda }\in \partial f(p)$ and $\frac{y-q}{\lambda }\in \partial f(q)$. Monotonicity of $\partial f$ (Proposition 4 of 44.02.05) gives $⟨\frac{x-p}{\lambda }-\frac{y-q}{\lambda },p-q⟩\ge 0$, i.e. $⟨(x-y)-(p-q),p-q⟩\ge 0$, which is $⟨p-q,x-y⟩\ge \Vert p-q{\Vert }^2$, the firm-nonexpansiveness inequality. Cauchy-Schwarz on the right then gives $\Vert p-q{\Vert }^2\le \Vert p-q\Vert \Vert x-y\Vert$, so $\Vert p-q\Vert \le \Vert x-y\Vert$. $\square$

Proposition 4 (Moreau envelope: smoothness and gradient). For proper closed convex $f$ and $\lambda >0$, $M_{\lambda f}$ is convex, finite, and continuously differentiable with $\nabla M_{\lambda f}(x)=\frac{1}{\lambda }(x-{\mathrm{prox}}_{\lambda f}(x))$, and this gradient is $\frac{1}{\lambda }$-Lipschitz.

Proof. $M_{\lambda f}(x)={\min }_u\{f(u)+\frac{1}{2\lambda }\Vert u-x{\Vert }^2\}$ is finite by Proposition 1 and convex as the infimal convolution of $f$ with the convex quadratic $\frac{1}{2\lambda }\Vert \cdot {\Vert }^2$ (an infimal convolution of convex functions is convex). Let $u(x)={\mathrm{prox}}_{\lambda f}(x)$. Fix $x$; for any $z$, using $M_{\lambda f}(z)\le f(u(x))+\frac{1}{2\lambda }\Vert u(x)-z{\Vert }^2$ and $M_{\lambda f}(x)=f(u(x))+\frac{1}{2\lambda }\Vert u(x)-x{\Vert }^2$,

$$M_{\lambda f}(z)-M_{\lambda f}(x)\le \frac{1}{2\lambda }(\Vert u(x)-z{\Vert }^2-\Vert u(x)-x{\Vert }^2)=⟨\frac{1}{\lambda }(x-u(x)),z-x⟩+\frac{1}{2\lambda }\Vert z-x{\Vert }^2.$$

The symmetric lower bound, obtained by swapping the roles of $x$ and $z$ and using $u(z)$, gives $M_{\lambda f}(z)-M_{\lambda f}(x)\ge ⟨\frac{1}{\lambda }(x-u(x)),z-x⟩-\frac{1}{2\lambda }\Vert z-x{\Vert }^2$ after combining; together these pin the gradient as $\nabla M_{\lambda f}(x)=\frac{1}{\lambda }(x-u(x))$. Lipschitz continuity: $\Vert \nabla M_{\lambda f}(x)-\nabla M_{\lambda f}(y)\Vert =\frac{1}{\lambda }\Vert (x-y)-(u(x)-u(y))\Vert$; firm nonexpansiveness (Proposition 3) makes $u$ such that $⟨u(x)-u(y),x-y⟩\ge \Vert u(x)-u(y){\Vert }^2$, so $I-u$ is also firmly nonexpansive, hence nonexpansive, giving $\Vert \nabla M_{\lambda f}(x)-\nabla M_{\lambda f}(y)\Vert \le \frac{1}{\lambda }\Vert x-y\Vert$. $\square$

Proposition 5 (Moreau decomposition). For proper closed convex $f$ with conjugate $f^{\ast }$, ${\mathrm{prox}}_f(v)+{\mathrm{prox}}_{f^{\ast }}(v)=v$ for all $v$.

Proof. Let $u={\mathrm{prox}}_f(v)$ and $w=v-u$. Proposition 2 (with $\lambda =1$) gives $v-u\in \partial f(u)$, i.e. $w\in \partial f(u)$. The subdifferential inversion for closed proper convex $f$, $g\in \partial f(u)⟺u\in \partial f^{\ast }(g)$ (Exercise 7 / Connections of 44.02.05, a consequence of $f^{\ast \ast }=f$ and the Fenchel-Young equality of 44.02.03), gives $u\in \partial f^{\ast }(w)$, i.e. $v-w\in \partial f^{\ast }(w)$. By Proposition 2 applied to $f^{\ast }$, this says $w={\mathrm{prox}}_{f^{\ast }}(v)$. Hence ${\mathrm{prox}}_f(v)+{\mathrm{prox}}_{f^{\ast }}(v)=u+w=v$. $\square$

Proposition 6 (sufficient-decrease lemma). Let $f$ be convex and $L$-smooth, $g$ proper closed convex, $0<t\le 1/L$, and $x^{+}={\mathrm{prox}}_{tg}(x-t\nabla f(x))$. Then for every $y$, $F(x^{+})\le F(y)+\frac{1}{2t}(\Vert x-y{\Vert }^2-\Vert x^{+}-y{\Vert }^2)$.

Proof. This is part (ii) of the Key theorem; the proof there is complete: combine the descent lemma (1) for $L$-smooth $f$ with $t\le 1/L$, the prox optimality $\frac{x-x^{+}}{t}-\nabla f(x)\in \partial g(x^{+})$ from Proposition 2, the subgradient inequality (2) for $g$ at $x^{+}$, and convexity of $f$ at $x$; the $\nabla f(x)$ cross-terms cancel and the polarisation identity $\frac{1}{2t}\Vert x^{+}-x{\Vert }^2-\frac{1}{t}⟨x-x^{+},y-x^{+}⟩=\frac{1}{2t}(\Vert x-y{\Vert }^2-\Vert x^{+}-y{\Vert }^2)$ delivers the bound. $\square$

Proposition 7 ($O(1/k)$ rate). Under Proposition 6's hypotheses with $x_{k+1}={\mathrm{prox}}_{tg}(x_k-t\nabla f(x_k))$ and $x^{\star }\in \arg \min F$, $F(x_k)-F^{\star }\le \Vert x_0-x^{\star }{\Vert }^2/(2tk)$.

Proof. Take $y=x^{\star }$ in Proposition 6 with $x=x_k$, $x^{+}=x_{k+1}$: $F(x_{k+1})-F^{\star }\le \frac{1}{2t}(\Vert x_k-x^{\star }{\Vert }^2-\Vert x_{k+1}-x^{\star }{\Vert }^2)\ge 0$, so the distance is nonincreasing and the suboptimalities telescope: ${\sum }_{i=0}^{k-1}(F(x_{i+1})-F^{\star })\le \frac{1}{2t}\Vert x_0-x^{\star }{\Vert }^2$. Take $y=x_k$, $x=x_k$, $x^{+}=x_{k+1}$ in Proposition 6: $F(x_{k+1})\le F(x_k)$, so the sequence $\{F(x_i)-F^{\star }\}$ is nonincreasing, whence $k(F(x_k)-F^{\star })\le {\sum }_{i=1}^k(F(x_i)-F^{\star })\le \frac{1}{2t}\Vert x_0-x^{\star }{\Vert }^2$. Divide by $k$. $\square$

Connections Master

• The proximal operator is the resolvent $(I+\lambda \partial f{)}^{-1}$ of the subdifferential built in 44.02.05: the second prox theorem $v-u\in \lambda \partial f(u)$ is Fermat's rule applied to the regularised objective, firm nonexpansiveness is the monotonicity of $\partial f$ proved there, and the Moreau decomposition ${\mathrm{prox}}_f+{\mathrm{prox}}_{f^{\ast }}=I$ is exactly the subgradient inversion $\partial f^{\ast }=(\partial f{)}^{-1}$ read at the resolvent level. The entire prox calculus is the algorithmic face of that unit's subdifferential theory.

• The Moreau decomposition and the conjugate-based prox calculus rest on the Fenchel conjugate and the Fenchel-Young equality of 44.02.03: ${\mathrm{prox}}_{f^{\ast }}$ is well-posed because $f^{\ast }$ is closed proper convex, and the cone special case $v=P_C(v)+P_{C^{\circ }}(v)$ is the indicator-conjugate pairing ${\iota }_C^{\ast }={\iota }_{C^{\circ }}$ specialised, so the duality of that unit is what makes the backward step splittable across $f$ and $f^{\ast }$.

• The proximal-gradient method is the direct successor to the subgradient method of 44.06.01: by splitting $F=f+g$ and replacing the subgradient step on the nonsmooth part by an exact prox step, it leaves the black-box model in which $O(1/\sqrt{k})$ is unimprovable and attains $O(1/k)$ from the descent lemma. The lower bound of that unit is precisely the barrier this structural exploitation circumvents, and the fixed-point condition $0\in \nabla f+\partial g$ is the composite Fermat rule those two units share.

Historical & philosophical context Master

The proximal operator and the regularisation now called the Moreau envelope were introduced by Jean-Jacques Moreau in a sequence of notes culminating in his 1965 paper Proximité et dualité dans un espace hilbertien ^{[Moreau 1965]}, where he defined ${\mathrm{prox}}_f$, established the decomposition ${\mathrm{prox}}_f+{\mathrm{prox}}_{f^{\ast }}=I$, and identified the prox as the resolvent of the subdifferential, then a maximal monotone operator in the sense being developed concurrently by Minty and Browder. The proximal point algorithm $x_{k+1}={\mathrm{prox}}_{\lambda f}(x_k)$ was analysed as a general method for monotone inclusions by R. Tyrrell Rockafellar in 1976 ^{[Rockafellar 1976]}, building on Bernard Martinet's 1970 introduction of the proximal regularisation for variational problems. The forward-backward splitting that interleaves an explicit gradient step with an implicit prox step traces to the operator-splitting work of Lions and Mercier (1979) and Passty (1979) on sums of monotone operators, and was brought into signal recovery and sparse regression by Combettes and Wajs ^{[Combettes & Wajs 2005]}. The composite $O(1/k)$ analysis and its $O(1/k^2)$ acceleration (FISTA) were given by Beck and Teboulle in 2009 ^{[Beck & Teboulle 2009]}, the source whose sufficient-decrease estimate this unit follows.

Bibliography Master

@book{beck2017fom,
  author    = {Beck, Amir},
  title     = {First-Order Methods in Optimization},
  series    = {MOS-SIAM Series on Optimization},
  number    = {25},
  publisher = {SIAM},
  year      = {2017}
}

@article{parikhboyd2014proximal,
  author  = {Parikh, Neal and Boyd, Stephen},
  title   = {Proximal Algorithms},
  journal = {Foundations and Trends in Optimization},
  volume  = {1},
  number  = {3},
  pages   = {127--239},
  year    = {2014}
}

@article{combetteswajs2005,
  author  = {Combettes, Patrick L. and Wajs, Val\'erie R.},
  title   = {Signal recovery by proximal forward-backward splitting},
  journal = {Multiscale Modeling \& Simulation},
  volume  = {4},
  number  = {4},
  pages   = {1168--1200},
  year    = {2005}
}

@article{becktebeoulle2009fista,
  author  = {Beck, Amir and Teboulle, Marc},
  title   = {A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems},
  journal = {SIAM Journal on Imaging Sciences},
  volume  = {2},
  number  = {1},
  pages   = {183--202},
  year    = {2009}
}

@article{moreau1965proximite,
  author  = {Moreau, Jean-Jacques},
  title   = {Proximit\'e et dualit\'e dans un espace hilbertien},
  journal = {Bulletin de la Soci\'et\'e Math\'ematique de France},
  volume  = {93},
  pages   = {273--299},
  year    = {1965}
}

@article{rockafellar1976proximal,
  author  = {Rockafellar, R. Tyrrell},
  title   = {Monotone operators and the proximal point algorithm},
  journal = {SIAM Journal on Control and Optimization},
  volume  = {14},
  number  = {5},
  pages   = {877--898},
  year    = {1976}
}

@book{bauschkecombettes2017,
  author    = {Bauschke, Heinz H. and Combettes, Patrick L.},
  title     = {Convex Analysis and Monotone Operator Theory in Hilbert Spaces},
  edition   = {2},
  series    = {CMS Books in Mathematics},
  publisher = {Springer},
  year      = {2017}
}