Proof that the difference between the input and output of the proximal operator belongs to the subdifferential

114 Views Asked by At

The proximal operator $\text{prox}$ is defined as follows, for a function $f$, at point $x$:

$$\text{prox}_f(x) = \underset{u}{\text{argmin}} (f(u) + \frac{1}{2} ||x-u||^2)$$

The subdifferential $\partial f(x)$ of a function $f$ at a point $x$ is the set of subgradients of $f$ at point $x$, where a subgradient is any vector such that the line generated by it is always under the function.

It is claimed that $\forall x \in \text{dom} (f), x - \text{prox}_f(x) \in \partial f(x)$, yet I can't figure out why.