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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Change the - sign to + sign, then read web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf . $\endgroup$
    – Mark L. Stone
    Jul 13, 2016 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, 2016 at 21:32
  • 3
    $\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, 2016 at 21:55
  • 1
    $\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, 2016 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, 2016 at 22:02

1 Answer 1

Reset to default
1
$\begingroup$

When $f$ is convex, the optimization problem to compute the prox is convex (in fact, strictly convex, because the least squares term is strictly convex).

The proximal gradient method (PGM) is a generalization of gradient descent (see Proximal Gradient Methods for Learning).
In some instances, it acts like gradient descent (or accelerated gradient descent) for optimizing composite models (sums of convex functions where one of them isn't differentiable).

In many fields (e.g., LASSO regression) proximal operators are useful and lead to effective algorithms.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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