Fenchel inequality with Proximal operator

Preliminaries

Let $h: H\rightarrow \mathbb R\cup{+\infty}$ be closed proper convex function on the Hilbert space $H$.

A vector $g\in H$ is called a subgradient of $h$ at $u_0\in H$ if
$$h(u) \geq h(u_0) +\langle g, u-u_0\rangle, \forall u\in H.$$
The set of all subgradients at $u_0$ is called subdifferential denoted by $\partial h(u_0)$. Thus the subdifferential can be considered as a set-value function, say
$$\partial h: H \rightrightarrows H$$

We shall identify $\partial h$ with its graph
$$\partial h \equiv \{(u, v): v\in \partial h(u)\}.$$

The conjugate function (a.k.a Fenchel conjugate or convex conjugate) of $h$ is $h^*: H\rightarrow \mathbb R\cup{+\infty}$ so that
$$h^*(v) \triangleq \sup_{u\in H} \langle v, u\rangle - h(u)$$

Theorem. [Basic Fenchel inequality]
$$h(u) +h^*(v)\geq \langle u, v\rangle$$
The equality holds if $(u, v)\in \partial h$.

The function $h$ is said to be $\alpha$-strongly convex if
$$h(u) \geq h(u_0) + \langle \partial h(u_0), u-u_0\rangle + \dfrac{\alpha}{2}||u-u_0||^2$$

If $h$ is strongly convex, the Fenchel inequality can be improved

Theorem. [Fenchel inequality with strong convexity] If $h$ is $\alpha$-strongly convex
$$h(u) +h^*(v)\geq \langle u, v\rangle + \frac{\alpha}{2}||u - \nabla h^*(v) ||^2.$$
The equality holds if $(u, v)\in \partial h$.

Here, It is well-known that if $h$ is $\alpha$-strongly convex, then $h^*$ is $1/\alpha$-strongly smooth (or usually known as $1/\alpha$-smooth), i.e.
$$\partial h^*(v) = \{\nabla h^*(v)\}, \forall v\in H,$$
and $\nabla h^*$ is $1/\alpha$-Lipschitz. Here $\nabla h^*$ is the Frechet differential of $h^*$.

Proof.
Let $$r = \nabla h^*(v).$$ We have
$$h(r) + h^*(v)= \langle r, v\rangle.$$

Since $h$ is $\alpha$-strongly convex, we have
$$h(u)- h(r)\geq \langle \partial h(r), u-r\rangle + \frac{\alpha}{2}||u-r||^2.$$

Take the sum and notice that $v\in \partial h(r)$ since $r=\nabla h^*(v)$, we have
$$h(u)+ h^*(v)\geq \langle v, u\rangle + \frac{\alpha}{2}||u-r||^2.$$
The proof is complete.

The equality holds if $u=r$, which is equivalent to $v\in \partial h(u)\Leftrightarrow (u, v)\in \partial h$.
$\square$

Fenchel inequality with Proximal operator

In this section we discuss a refined version of Fenchel inequality using proximal operator.
The main reference here is [1, Lemma 1.1, epage 3].

Theorem. [Fenchel inequality with proximal operator] For $\lambda>0$, we have
$$h(u) +h^*(v)\geq \langle u, v\rangle + \frac{1}{\lambda}||u - prox_{\lambda h}(u + \lambda v) ||^2$$
The equality holds if
$$prox_{\lambda h}(u+\lambda v)\in \lambda \partial h^*(v) \text{ and } (u +\lambda v) − prox_{\lambda h}(u +\lambda v) ∈ \lambda \partial h(u).$$

We now discuss the application of above inequality for strongly convex function $h$, i.e.

Remark. Fenchel inequality with proximal operator implies a “weak version” Fenchel inequality with strong convexity

For the ease of notations, we introduce the dual gap. For $u, v\in H$, the dual gap of $u, v$ w.r.t $h$ is
$$gap(u, v) \triangleq h(u)+h^*(v) - \langle u, v\rangle.$$
From the basic Fenchel inequality, we know that the dual gap is always non-negative.
We now show that

Theorem. If $h$ is $1$-strongly convex, we have
$$gap(u, v) \geq ||u - prox_{h}(u +v) ||^2\geq \textcolor{blue}{\frac{1}{4}} ||u-r||^2$$
where $r = \nabla h^*(v).$

Proof.

For $v\in H$, define
$$r\triangleq \nabla h^*(v).$$
Since $h^*$ is closed proper convex, we also have
$$v\in \partial h(r).$$

Moreover, denote
$$J = prox_{h}$$

So, we now aim to show that
$$||u - J(u +v) ||^2\geq \frac{1}{4}||u-r||^2.$$

Observe that $r = (id + \partial h)^{-1} (id +\partial h) r = prox_{h}(r+ v) = J(r+v)$, see the theorem in the Appendix for the relation between proximal operator and subdifferential.

Thus, we have
$$||u - J(u +v) ||^2 = ||[(u+v) - J(u+v)] - [(r+v) - J(r+v)] ||^2$$
Also notice that $\nabla M_{h} (w)= w-Jw$, see Appendix for the relation between proximal operator and gradient of Moreau function. We now have
$$||[(u+v) - J(u+v)] - [(r+v) - J(r+v)] ||^2=||\nabla M_{h}(u+v) -\nabla M_{h}(r+v) ||^2$$

On the other hand, since $h$ is $\alpha$-strongly convex ($\alpha=1$). The Moreau function is $\dfrac{\alpha}{1+\alpha}$-strong convex, see [2, Lemma 2.19, epage 6]. Therefore, by [3, Lemma 3 ii), epage 3]
$$||\nabla M_{h}(u+v) -\nabla M_{h}(r+v) ||^2\geq \frac{1}{4}||u-r||^2.$$

Appendix: Proximal operator

The Moreau function of $h$ with parameter $\lambda>0$ is $M_{\lambda h}: H\rightarrow \mathbb R\cup\{+\infty\}$ defined by

$$M_{\lambda h}(v) = \min_{u\in H} \lambda h(u) + \frac{1}{2}||u-v||^2$$

Note that the $\min$ is well-defined.

The (unique) argmin of the RHS is called the proximal of $v$
$$prox_{\lambda h} (v) = \argmin_{u\in H} \lambda h(u) + \frac{1}{2}||u-v||^2$$

Example. Let $K\subset H$, we have
$$prox_{\lambda \iota_K} = proj_K$$
and
$$M_{\lambda \iota_K}(v) =\frac{1}{2} dist(v, K)^2$$

Example. Let $h(u) = \frac{1}{2}||b-u||^2$, we have
$$prox_{h}(v) = \frac{b+v}{2}$$
and
$$M_h(v) = \frac{1}{4}||b-v||^2$$

The proximal operator has some representations:

Theorem. [connection with subdifferential]
$$prox_{\lambda h} = (id + \lambda \partial h)^{-1}$$

Proof. Let $v\in H$ and $w=prox_{\lambda h}(v)$, we have
$$0\in \lambda \partial h(w) + w-v$$
that is
$$v\in w+ \lambda \partial h(w) = (id+\lambda \partial h)(w)$$
or
$$w \in (id+ \lambda \partial h)^{-1}(v)$$
$\square$

Theorem. [connection with Gradient of Moreau function]
$$\nabla M_{\lambda h}(v) = \frac{1}{\lambda} (v - prox_{\lambda h}(v)).$$

Proof. See [2, Fact 2.9, epage 4]

Theorem. The gradient of Moreau function is always $1$-Lipschitz
$$||\nabla M_{\lambda h} (u)- \nabla M_{\lambda h}(v)||\leq ||u-v||$$

Proof. See [2, Fact 2.9, epage 4]

Theorem. If $h$ is $\alpha$-strongly convex, then the Moreau function is $\frac{\alpha}{1+\alpha}$-strongly convex, thus
$$||\nabla M_{\lambda h} (u)- \nabla M_{\lambda h}(v)|| \textcolor{red}{\geq} \textcolor{blue}{\frac{\alpha}{1+\alpha}} ||u-v||$$

Proof. See [2, Lemma 2.19, epage 6] and [3, Lemma 3 ii), epage 3].

References

[1]: Carlier, Guillaume. “Fenchel-Young inequality with a remainder and applications to convex duality and optimal transport.” (2022).
[2]: Planiden, Chayne, and Xianfu Wang. “Strongly convex functions, Moreau envelopes, and the generic nature of convex functions with strong minimizers.” SIAM Journal on Optimization 26.2 (2016): 1341-1364.
[3]: Zhou, Xingyu. “On the fenchel duality between strong convexity and lipschitz continuous gradient.” arXiv preprint arXiv:1803.06573 (2018).

---