Consider a proximal operator,

$$ \operatorname{Prox}_{ \lambda f( u ) } \left( x \right) = \arg \min_{u} \lambda f \left( u \right) + \frac{1}{2} {\left\| u - \mu x \right\|}_{2}^{2}.$$

What is the partial derivative of the proximal operator w.r.t. $\lambda$ and $\mu$, i.e.

$$\frac{\partial\operatorname{Prox}_{ \lambda f( u ) } \left( x \right)}{\partial\lambda}, \quad \frac{\partial\operatorname{Prox}_{ \lambda f( u ) } \left( x \right)}{\partial\mu}?$$

If the general case is not solvable, is it possible to compute the derivative if we restrict $f$ to be an $L_p$ norm?

  • $\begingroup$ I think this is an interesting question. $\endgroup$
    – littleO
    Aug 30 '19 at 7:47
  • $\begingroup$ I don't think that it is differentiable w.r.t. $\mu$. In case that $f$ is an indicator function, the prox is just the projection. Projections are, in general, not differentiable w.r.t. $x$. $\endgroup$
    – gerw
    Aug 30 '19 at 9:15

The prox operator takes a point (vector) and maps it into a subset of your vector space, this mapping might be empty, a singleton or a set. Therefore the prox operator is not differentiable.

The following example is from the book by Beck. Consider the following functions: \begin{align} g_1(x) &=0, \\ g_2(x)&=\begin{cases} 0 & x \neq 0\\ - c & x=0, \end{cases}\\ g_3(x)&=\begin{cases} 0 & x \neq 0\\ c & x=0, \end{cases} \end{align} then the prox of the previous functions is:

\begin{align} \text{prox}_{g_1}(x)&=\{x\}.\\ \text{prox}_{g_2}(x)&=\begin{cases} \{0\}, & |x| < \sqrt{2c},\\ \{x\}, & |x| > \sqrt{2c}, \\ \{0,x\}, & |x| = \sqrt{2c}. \end{cases}\\ \text{prox}_{g_3}(x)&=\begin{cases} \{0\} & x \neq 0,\\ \emptyset & x=0. \end{cases} \end{align}

On the other hand, the Moreau envelope, defined as $$M^{\mu}_f(x) = \inf_{y}\bigg\{f(y)+\frac{1}{2\mu} ||x-y||^2 \bigg\},$$ is a smooth map (in fact $\mu$ is called the smoothing parameter), therefore it makes sense to talk about differentiability. The derrivate of the Moreau envelope is $$\nabla M^{\mu}_f(x) = \frac{1}{\mu}(x - \text{prox}_{\mu f}(x)).$$

You can read more on the excellent books by Beck (Ch. 6) and Bauschke & Combettes (Ch. 12).

  • $\begingroup$ But if we assume that $f:\mathbb R^n \to \mathbb R$ is closed and convex then $\text{prox}_{tf}(x)$ is guaranteed to be a singleton, so the proximal operator of $f$ can be viewed as a function from $\mathbb R^n$ to $\mathbb R^n$. I bet OP would be willing to make this assumption. $\endgroup$
    – littleO
    Aug 31 '19 at 20:48
  • $\begingroup$ That's a great answer to the general case! As @littlO is saying, I'd be willing to assume that $f$ is closed and convex (e.g. if it is an Lp norm). $\endgroup$
    – w382903
    Sep 2 '19 at 13:00

For the restricted case where $f$ is differentiable one can derive a solution. First, the derivative w.r.t. to $\lambda$ is

$$\frac{\partial\operatorname{Prox}_{ \lambda f( u ) } \left( x \right)}{\partial\lambda} = \lim_{\epsilon\to 0}\frac{1}{\epsilon}\left[\operatorname{Prox}_{ (\lambda + \epsilon) f( u ) } \left( x \right) - \operatorname{Prox}_{ \lambda f( u ) } \left( x \right)\right]$$

The solution to $\operatorname{Prox}_{ (\lambda + \epsilon) f( u ) } \left( x \right)$ can be computed from a simple Taylor expansion. In particular, any solution has to fulfill

$$(\lambda + \epsilon) \nabla f(u) + (u - \mu x) = 0$$ $$\Leftrightarrow (\lambda + \epsilon) \nabla f(u^{*} + du) + u^{*} + du - \mu x = 0$$

where $u^{*} = \operatorname{Prox}_{ \lambda f( u ) } \left( x \right)$. Then, with $H_f(u^{*})$ being the Hessian of $f$,

$$\Leftrightarrow (\lambda + \epsilon) (\nabla f(u^{*}) + H_f(u^{*}) du) + u^{*} + du - \mu x = 0$$

$$\Leftrightarrow \epsilon \nabla f(u^{*}) + (\lambda + \epsilon) H_f(u^{*}) du + du = 0$$


$$du = -\epsilon\left[(\lambda + \epsilon)H_f(u^{*}) + I\right]^{-1}\nabla f(u^{*})$$

$$\Rightarrow \frac{\partial\operatorname{Prox}_{ \lambda f( u ) } \left( x \right)}{\partial\lambda} = -\left[\lambda H_f(u^{*}) + I\right]^{-1}\nabla f(u^{*})$$

In a very similar way we can find

$$\frac{\partial\operatorname{Prox}_{ \lambda f( u ) } \left( x \right)}{\partial\mu} = \left[\lambda H_f(u^{*}) + I\right]^{-1} x$$


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.