4
$\begingroup$

I'm trying to come up with a super simple proof of convergence on the proximal point algorithm, which uses the iteration scheme

$x^{i+1} = \mathbf{prox}_{tf}(x^i)$

where $f$ is a closed, convex (but not necessarily smooth) function and

$\mathbf{prox}_{tf}(z) = \arg\min_x f(x) + \frac{1}{2t}\|x-z\|_2^2$.

It's clear that if $x^i = x^{i+1}$ then $x$ must minimize $f$ (since the optimality condition $0\in \partial f(x)$ is satisfied; however, I have a small snafu when it comes to showing that a fixed point solution will be reached.

I think it's most elegant to use the fact that the proximal operator is firmly nonexpansive, that is, taking $u = \mathbf{prox}_{tf}(x)$ and $v = \mathbf{prox}_{tf}(y)$,

$(u-v)^T(x-y) \geq \|u-v\|_2^2$.

Via Cauchy-Schwarz, we have $\|x-y\|\geq \|u-v\|$. In other words

$\|x^i-x^{i-1}\|\geq \|x^{i+1}-x^i\|$

which is so close, but that $\leq$ is bothering me! I feel like there's some detail I'm missing, which is that if prox is firmly nonexpansive, I should be able to use some kind of strict inequality somewhere, to show that we can't ever have $\|x^i-x^{i-1}\|= \|x^{i+1}-x^i\|$.

I'm rereading Eckstein and Bertsekas "On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators" but I'm not quite getting how they got around this problem. Anybody know what I'm missing?

Thank you!

Edit: A better way to frame the overall question is to show that, if $A:\mathbb R^n\to 2^{\mathbb R^n}$ is a firmly nonexpansive operator, ie satisfying

$(u-v)^T(x-y)\geq \|u-v\|_2^2$

for all $x$, $y$, $u\in A(x)$, $v\in A(y)$, then the iteration scheme

$x^{i+1} = A(x^i)$

converges to a fixed point solution.

That way, the solution extends beyond the proximal point method to its splitting variants as well (forward-backward, Douglas-Rachford, etc.) (This is equivalent to Eckstein/Bertsekas' Theorem 3, but I was hoping for a simpler proof :) )

$\endgroup$
  • 1
    $\begingroup$ Ok so there is actually a very nice, short proof for this! And it doesn't quite use the construct I proposed, it basically proves that if $x^\star$ is the fixed point solution, then $\|x^{i+1}-x^\star\| < \|x^i - x^\star\|$. However, the proof is in my class notes and have not been made available to the public so I can't just post them! But in the rare case that there's someone dying of curiosity I could probably send it through message. Eckstein/Bertsekas' paper also gives a nice proof, but it just is a bit more complicated. $\endgroup$ – Y. S. May 28 '15 at 23:41
  • $\begingroup$ You have a typo in your question, it would be $||x^{i+1}-x^i||\leq ||x^i-x^{i-1}||$, not the opposite inequality. $\endgroup$ – Michael May 29 '15 at 4:14
  • $\begingroup$ Though, it is not obvious to me how to prove $(u-v)^T(x-y)\geq ||u-v||^2$. If true, I think my claim 3 could remove the compactness assumption on $X$, since the iterations would stay in a bounded region anyway. $\endgroup$ – Michael May 29 '15 at 4:16
  • 1
    $\begingroup$ Oh I figured it out, at least when gradients exist. You use $\nabla f(u) + (1/t)(u-x)=0$ and $\nabla f(v) + (1/t)(v-y)=0$, combining gives $(x-y)=(u-v) + t(\nabla f(u) - \nabla f(v))$, and use $(u-v)^T(\nabla f(u) - \nabla f(v)) \geq 0$ for convex functions. $\endgroup$ – Michael May 29 '15 at 5:01
  • 1
    $\begingroup$ @Michael the extension to nondifferentiable functions basically follows the same proof, but replaces $\nabla f$ with $\partial f$, which by definition also satisfies the first order condition: $g\in \partial f(x)\Rightarrow (f(y)-f(x)) \geq g^T(y-x)$, and have the characteristic that $(u-x)/t\in \partial f \iff u = \mathbf{prox}_{tf}(x)$. Also, again, I'm only assuming convex $f$ (because as your solution nicely shows, all bets are off if $f$ is nonconvex.) $\endgroup$ – Y. S. May 29 '15 at 20:45
6
$\begingroup$

I think you need to assume convexity of $f(x)$.

Given $x_i \in X$, define the iteration: $$ x_{i+1} = \arg\min_{x\in X}\left[f(x) + \frac{1}{2t}||x-x_i||^2\right] $$

Claim 1: Suppose $f(x)$ is a convex function over the convex set $X$ and has a global minimum $x^* \in X$. If $x_{i+1}=x_i$, then $x_{i+1}$ minimizes $f(x)$ over $X$.

Proof: Fix $\theta \in (0,1)$. Then $\theta x^* + (1-\theta) x_i \in X$. By definition of $x_{i+1}$ as minimizer of $f(x) + \frac{1}{2t}||x-x_i||^2$, it gets a value less than or equal to that of $(\theta x^* + (1-\theta) x_i)$, so: \begin{align} &f(x_{i+1}) + \frac{1}{2t}||x_{i+1}-x_i||^2 \\ &\leq f(\theta x^* + (1-\theta)x_i) + \frac{1}{2t}||(\theta x^* + (1-\theta)x_i) - x_i||^2 \\ &= f(\theta x^* + (1-\theta)x_i) + \frac{\theta^2}{2t}||x^*-x_i||^2 \\ &\leq \theta f(x^*) + (1-\theta)f(x_i) + \frac{\theta^2}{2t}||x^*-x_i||^2\\ &= \theta f(x^*) + (1-\theta)f(x_{i+1}) + \frac{\theta^2}{2t}||x^*-x_i||^2 \end{align} where the second-to-last inequality uses convexity of $f(x)$, and the last equality uses the fact that $x_i=x_{i+1}$. Note that $\theta>0$. Rearranging terms gives: $$ f(x_{i+1}) \leq f(x^*) + \frac{\theta}{2t}||x^*-x_i||^2 $$ This holds for all $\theta \in (0,1)$. Taking a limit as $\theta\rightarrow 0$ gives $f(x_{i+1}) \leq f(x^*)$. $\Box$


Claim 2: If $f(x_i)=f(x^*)$ for some iteration $i$, then $f(x_k)=f(x^*)$ for all iterations $k\geq i$.

Proof: Since $x_{i+1} \in X$ we have: $$ f(x^*) \leq f(x_{i+1}) \leq f(x_{i+1}) + \frac{1}{2t}||x_{i+1}-x_i||^2 \leq f(x_i) + \frac{1}{2t}||x_i-x_i||^2 = f(x_i) = f(x^*) $$ and so $f(x_{i+1})=f(x^*)$. The result follows by induction. $\Box$


Now define the error $\Delta_i = f(x_i) - f(x^*)$. Note that $\Delta_i\geq 0$ for all $i$. Assume the set $X$ is compact and $R = \sup_{x_1, x_2 \in X} ||x_1-x_2||$. To avoid trivialities, assume $R>0$.

Claim 3: Suppose $f(x)$ is a convex function over the convex set $X$ and has a global minimum $x^*\in X$. Then for all $\theta \in [0,1]$ we have: $$ \Delta_{i+1} \leq (1-\theta)\Delta_i + \frac{\theta^2R^2}{2t} $$

Proof: Fix $\theta \in [0,1]$. By a similar argument we have: \begin{align} &f(x_{i+1}) + \frac{1}{2t}||x_{i+1}-x_i||^2 \\ &\leq f(\theta x^* + (1-\theta)x_i) + \frac{1}{2t}||(\theta x^* + (1-\theta)x_i) - x_i||^2 \\ &= f(\theta x^* + (1-\theta)x_i) + \frac{\theta^2}{2t}||x^*-x_i||^2 \\ &\leq \theta f(x^*) + (1-\theta)f(x_i) + \frac{\theta^2}{2t}||x^*-x_i||^2\\ \end{align} Subtracting $f(x^*)$ from both sides gives: $$ \Delta_{i+1} \leq (1-\theta)\Delta_i + \frac{\theta^2R^2}{2t} $$ $\Box$

You can optimize the bound $(1-\theta)\Delta_i + \frac{\theta^2R^2}{2t}$ over $\theta \in [0,1]$ to get $\theta^* = \left[\frac{t\Delta_i}{R^2}\right]_0^1$. This gives two regimes:

i) Regime 1: Suppose $t\Delta_i/R^2 \geq 1$. Then $\theta^*=1$ and the bound from Claim 3 gives: $$ \Delta_{i+1} \leq \frac{R^2}{2t} < \frac{R^2}{t} $$ so we exit regime 1 after just 1 step.

ii) Regime 2: Suppose $0\leq t \Delta_i/R^2 < 1$. Then $\theta^*=t\Delta_i/R^2$ and the bound gives: $$ \Delta_{i+1} \leq \Delta_i - \frac{t\Delta_i^2}{2R^2} \implies \: \mbox{ if $\Delta_i>0$ then} \: \frac{\Delta_{i+1}}{\Delta_i} \leq 1 - \frac{t\Delta_i}{2R^2} < 1 $$ So the error cannot increase in this regime. Once we enter regime 2 we never leave. The error $\Delta_i$ also converges to 0. To see this, fix $\epsilon>0$. If the error ever gets less than $\epsilon$, then it stays less than $\epsilon$. If not, then $\Delta_i\geq \epsilon$ for all $i$ in regime 2, and so the regime 2 bound gives $\Delta_{i+1}/\Delta_i \leq 1 - \frac{t\epsilon}{2R^2}$ for all $i$, so we decay exponentially, which means we will eventually get smaller than $\epsilon$ (a contradiction). So we always eventually get smaller than $\epsilon$, this holds for all $\epsilon>0$.


Here is a counter-example to show that we may not converge to the global min, and we may not even move, when the function $f(x)$ is nonconvex. Define $f(x)$ as a function such that:

i) $f(x)$ has a unique minimum over the interval $(-\infty, 2]$ of $f(0)=0$.

ii) $f(x)$ has a minimum over the interval $(2, \infty)$ of $f(3)=-1$.

Suppose $t=1/2$ and $x_0=0$. We have $x_{i+1} = \min_{x\in\mathbb{R}} [f(x) + ||x-x_i||^2]$. Suppose $x_i=0$ (this is true for $x_0$). We show that $x_{i+1}=0$ also, so (by induction) we never move, and we never converge to the true global min $f(3)=-1$. Since $x_i=0$, we consider minimizing $f(x) + ||x-0||^2$:

-If $x \in (-\infty, 2]$ then $f(x) + ||x-0||^2 \geq f(0)+0 = 0$.

-If $x \in (2, \infty)$ then $f(x) + ||x-0||^2 \geq -1 + 2^2 = 3 > f(0)$.

It follows that $x_{i+1} = 0$. $\Box$

Another counter-example is if $f(x)=-(1/2)x^2$ and $t = 1/2$. Then if $x_0=0$ we get $x_1 = \arg\min_{x\in\mathbb{R}}[ f(x) + ||x-0||^2] = \arg\min_{x \in \mathbb{R}} \frac{x^2}{2} = 0$. So we stay at the global maximum of $f(x)$ (the infimum of $f(x)$ is $-\infty$).

$\endgroup$
  • 2
    $\begingroup$ Note that $x$ minimizes a closed convex function $f$ $\iff 0 \in \partial f(x) \iff x \in (I + t\partial f)(x) \iff x = (I + t \partial f)^{-1}(x) \iff x = \text{prox}_{tf}(x)$. That's a different proof that the minimizers of $f$ are exactly the fixed points of the prox-operator of $f$. $\endgroup$ – littleO May 29 '15 at 1:23
  • $\begingroup$ I see an unexplained down vote. Any reason? $\endgroup$ – Michael May 29 '15 at 3:38
  • $\begingroup$ @littleO , what is $I$? The identity matrix? And if $\partial f$ represents a subgradient vector, it is a vector, yet you treat it as a matrix that can be inverted? I do not get your proof. $\endgroup$ – Michael May 29 '15 at 4:23
  • 1
    $\begingroup$ Yes, that's a good way to say it. And also the function $y \mapsto f(y) + \frac{1}{2t} \| y - x \|^2$ is guaranteed to have a unique minimizer (when $f$ is closed and convex), so we could write $x = \text{prox}_{tf}(x)$ rather than $x \in \text{prox}_{tf}(x)$. $\endgroup$ – littleO May 29 '15 at 5:36
  • 1
    $\begingroup$ More details for the proof: $X$ is not usually compact since we assume $x\in \mathbb R^n$, but I think that assumption is ok because it turns out $\|x^{i+1}-x^\star\| \leq \|x^i - x^\star\|$ so you can say that $X$ is bounded by a ball of radius $\|x^0-x^\star\|$ centered at $x^\star$. $\endgroup$ – Y. S. May 29 '15 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.