0
$\begingroup$

I have been researching and the proximal operator seems to be defined as:

$$\DeclareMathOperator*{\argmin}{argmin}\DeclareMathOperator{\prox}{prox} \prox_f(v)=\argmin_x\left(f(x)+\frac{1}{2}\|x-v\|^2_2\right)$$

I have found it stated several times that this is always a convex problem with a unique minimizer. I have not, however, been able to find a proof of this statement. So, why does the proximal operator have a unique solution?

In addition, this article (link credit Mark L. Stone, see comments) hints that $f(x)$ must be convex for the proximal operator to be a convex problem. If this condition is required by the proof, why would someone use proximal optimization methods over simple gradient descent?

$\endgroup$
  • 1
    $\begingroup$ Change the - sign to + sign, then read web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf . $\endgroup$ – Mark L. Stone Jul 13 '16 at 19:35
  • $\begingroup$ Thanks. I have read that PDF with a little more detail than before posting now, but I still don't see an exact answer to my main question in there. I'll edit the question with respect to what I found on the second read of that link though. $\endgroup$ – KFox Jul 13 '16 at 21:32
  • 2
    $\begingroup$ If $f(x)$ is convex, then the proximal operator is strictly convex; so has a unique global minimum. It's possible that the proximal operator could be convex, even if $f(x)$ is not. The main attraction of proximal operator methods seems to be dealing with convex, but non-differentiable, $f(x)$, for which gradient-based methods aren't directly applicable (in reality, methods such as BFGS can sometimes "blast' their way through or past isolated non-differentiable points, if not at the optimum). Proximal operator becomes attractive when prox problems are easy to solve (maybe even in closed form).. $\endgroup$ – Mark L. Stone Jul 13 '16 at 21:55
  • $\begingroup$ I recently learned that the sum of two convex functions (even with different domains) is convex. This, in combination with your comment, answers my question. Thanks! $\endgroup$ – KFox Jul 13 '16 at 21:59
  • 1
    $\begingroup$ If you make it through chapters 2 and 3 of stanford.edu/~boyd/cvxbook (by one of the same authors as the paper), you'll understand much more complicated operations than addition which preserve convexity. $\endgroup$ – Mark L. Stone Jul 13 '16 at 22:02
1
$\begingroup$

The Prox operator you wrote assumes $ f \left( \cdot \right) $ is a Convex Function.
As when it does, the whole problem is Convex (Even Strictly Convex as the Least Squares term is Strictly Convex).

The Proximal Gradient Method (PGM) is a generalization of the Gradient Descent (See Proximal Gradient Methods for Learning).
It is able to provide performance of the Gradient Descent (Even the Accelerated Gradient Descent) for the Composite Model (Sum of Convex functions yet one of them isn't Differentiable).

In many fields (Like Lasso Regression) this property is useful and using this tool yields great and effective algorithms.

$\endgroup$

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.