convexity_and_smoothness

On the Duality Between Uniform Convexity and Uniform Smoothness

The duality result between strong convexity and strong smoothness is a well known result, see e.g. [1]. A generalization of this duality is a duality result between more general concepts uniform convexity and uniform smoothness, its proof can be found e.g. in the book of Zalinescu [3, Prop. 3.5.3]. Although the proof idea of Zalinescu is correct, there are some errors and typos in the definitions, theorem statement and even the proof. In this note, we revisit and rigorously prove this result of Zalinescu.

More importantly, we show that
$$\text{uniform convexity on domain} \Longleftrightarrow \text{uniform smoothness on entire space.}$$

As a consequence
$$\text{strong convexity on domain} \Longleftrightarrow \text{strong smoothness on entire space.}$$

1. Basic concepts

Let $(X, ||\cdot||)$ be a normed space and $(X^*, ||\cdot||_*)$ be its continuous dual space. Let $\mathcal{A}_X$ be class of non-negative vector-variable functions vanishing at $0$, i.e. $\mathcal{A}_X=\{\varphi: X\rightarrow [0, +\infty] \text{ so that } \varphi(0)=0\}$. Here, note that we do not assume that the functions in $\mathcal A_X$ are symmetric.

For $f: X\rightarrow [-\infty, +\infty]$, its convex conjugate $f^*: X^*\rightarrow [-\infty, +\infty]$ is defined as follows

$$f^*(x^*)=\sup_{x\in X} \quad \langle x^*, x\rangle-f(x)$$

It is clear that if $\varphi\in \mathcal{A}_X$, then $\varphi^*\in \mathcal{A}_{X^*}$.

For $\rho\in \mathcal A_X$, $f$ is said to be $\rho$-uniformly convex on its domain $dom f$, if

$$f((1-\lambda)x+\lambda y)+ (1-\lambda)\lambda \textcolor{blue}{\rho(x-y)}\textcolor{red}{\leq}(1-\lambda)f(x)+\lambda f(y)$$

for all $x, y\in dom f$ and $\lambda \in [0,1]$. By the non-negativity of $\rho$, uniform convexity implies convexity. When $\rho(x)=\frac{\alpha}{2}||x||^2_X$, $f$ is said to be $\alpha$-strongly convex.

Similarly, for $\sigma\in \mathcal A_X$, $f$ is said to be $\sigma$-uniformly smooth if it is convex and satisfies

$$f((1-\lambda)x+\lambda y)+ (1-\lambda)\lambda \textcolor{blue}{\sigma(x-y)}\textcolor{red}{\geq} (1-\lambda)f(x)+\lambda f(y)$$

for all $x, y\in dom f$, $\lambda \in [0,1]$. When $\sigma(x)=\frac{\beta}{2}||x||^2_X$, $f$ is said to be $\beta$-strongly smooth. In particular, we say that $f$ is globally $\sigma$-uniformly smooth, if it is $\sigma$-uniformly smooth and $dom f= X$.

In the following, we will exploit the following transformation:

$$\begin{cases} x' = (1-\lambda)x + \lambda y\\ y ' = -x+y\end{cases} \Longleftrightarrow \begin{cases} x = x' - \lambda y'\\ y = x' + (1-\lambda) y'\end{cases}$$

By this transformation, $\sigma$-uniform smoothness has an equivalent definition

$$f(x')+ (1-\lambda)\lambda \textcolor{blue}{\sigma(-y')}\geq (1-\lambda)f(x'-\lambda y')+\lambda f(x'+(1-\lambda)y'),$$

for all $x', y'\in X$ and $\lambda\in [0,1]$ such that $x'-\lambda y'$ and $x' + (1-\lambda)y' \in dom f$.

Remark. Note that if $f$ is uniformly smooth, then the Frechet derivative of $f$ exists and is uniformly continuous, see Theorem 3.5.6. page (xi) 207-208 [3]. The existence of Frechet derivative explains why we call it smoothness. Furthermore, if $f$ is strongly smooth, then the Frechet derivative is even Lipschitz continuous, see Corollary 3.5.7. page 212-213 (vi) [2].

2. Duality Result

Theorem (Revise [3, Prop. 3.5.3])
Assume that $f$ is a closed proper convex function.

• If $f$ is $\rho$-uniformly convex on $dom f$, then $f^*$ is $\rho^*$-uniformly smooth on $X^*$.
• If $f$ is $\sigma$-uniformly smooth on $X$, then $f^*$ is $\sigma^*$-uniformly convex on $dom f^*$.

Proof.

(s.convex $\Rightarrow$ s. smooth) Assume that $f$ is $\rho$-uniformly convex.

Note that
$$\partial f^*(x^*) = \argmax_{x\in X} \langle x^*, x\rangle -f(x), \quad \forall x^*\in X^*.$$
Since $f$ is closed, proper and uniformly convex, the argmax is well-defined and singleton. So is $\partial f^*$. Thus, $f^*$ is differentiable everywhere on $X^*$ and $dom f^* =X^*$.

Let $x_0^*, x_1^* \in X^*$ be arbitrary and $\lambda\in [0,1]$.

To prove that $f^*$ is globally $\rho^*$-uniformly smooth, we show that

$$(1-\lambda)f^*(x_0^*)+\lambda f^*(x_1^*)\leq f^*(x^*)+ \lambda(1-\lambda) \rho^*(-y^*).$$

where $x^* := (1-\lambda) x^*_0+ \lambda x_1^*$ and $y^* := -x_0^*+x_1^*$. Conversely, we have $x_0^*:=x^*-\lambda y^*$ and $x_1^*:=x^*+(1-\lambda)y^*$.

Let $\gamma_0<f^*(x_0^*)$ and $\gamma_1<f^*(x_1^*)$. By definition of conjugate, there exist $x_0, x_1\in dom f$ such that $\gamma_0<\langle x_0, x_0^*\rangle - f(x_0)$ and $\gamma_1<\langle x_1, x_1^*\rangle - f(x_1)$. Multiplying the first inequality by $1-\lambda$ and the second by $\lambda$ and then adding both side to Fenchel’s inequality, $0\leq f(x_\lambda)+f^*(x^*)-\langle x_\lambda, x^*\rangle$, where $x_\lambda=(1-\lambda)x_0+\lambda x_1$, we can end up with

$$\begin{aligned}(1-\lambda)\gamma_0+\lambda \gamma_1 <& (1-\lambda)[\langle x_0, x_0^*\rangle - f(x_0)] + \lambda [\langle x_1, x_1^*\rangle - f(x_1)] \\ & + f(x_\lambda)+f^*(x^*)-\langle x_\lambda, x^*\rangle\\ = & f^*(x^*) + [f(x_\lambda) - (1-\lambda) f(x_0) - \lambda f(x_1)]\\ &+ (1-\lambda)\langle x_0, x_0^*\rangle + \lambda \langle x_1, x_1^*\rangle - \langle x_\lambda, x^*\rangle\\ \leq & f^*(x^*) + \lambda(1-\lambda)[ \langle x_1-x_0, y^* \rangle - \rho(x_0-x_1)] \\ = & f^*(x^*) + \lambda(1-\lambda)[ \langle x_0-x_1, -y^* \rangle - \rho(x_0-x_1)] \\ \leq & f^*(x^*)+ \lambda(1-\lambda) \rho^*(-y^*).\end{aligned}$$

Here, we implicitly apply the fact that $f$ is $\rho$-uniformly convex at the second inequality. Taking $\gamma_i\rightarrow f^*(x^*_i)$ for $i=1,2$, the $\rho^*$-uniform smoothness of $f^*$ is proved.

(s.smooth $\Rightarrow$ s.convex) Suppose that $f$ is globally $\sigma$-uniformly smooth. Let any $x_0^*, x_1^*\in dom f^*$ and $\lambda \in [0,1]$. Denote $x_\lambda^* := (1 - \lambda)x_0^*+\lambda x_1^*$. For any $x, y \in X$, we have

$$\begin{aligned}& (1-\lambda)f^*(x_0^*)+\lambda f^*(x_1^*)\\ \geq & (1-\lambda) [\langle x-\lambda y, x_0^*\rangle -f(x-\lambda y)] + \lambda [ \langle x+(1-\lambda) y, x_1^*\rangle -f(x+(1-\lambda) y) ]\\ =& [\langle x, x^*_\lambda\rangle + \lambda(1-\lambda) \langle y, x_1^*-x_0^*\rangle] -[(1-\lambda) f(x-\lambda y) + \lambda f(x+(1-\lambda) y)] \\ \geq & [\langle x, x^*_\lambda\rangle + \lambda(1-\lambda) \langle y, x_1^*-x_0^*\rangle] -[f(x) + \lambda (1-\lambda) \sigma(-y)] \\ =& \langle x, x^*_\lambda\rangle - f(x) + \lambda(1-\lambda) [\langle y, x_1^*-x_0^*\rangle - \sigma(-y)]\\ =& \langle x, x^*_\lambda\rangle - f(x) + \lambda(1-\lambda) [\langle -y, x_0^*-x_1^*\rangle - \sigma(-y)]\end{aligned}$$

Here, the second inequality holds since $f$ is assumed to be globally $\sigma$-uniformly smooth.

Since the result holds for any $x, y\in X$, we may take the supremum and obtain

$$(1-\lambda)f^*(x_0^*)+\lambda f^*(x_1^*) \geq f^*(x^*_\lambda) + \lambda (1-\lambda)\sigma^*(x_0^*-x_1^*).$$

Therefore, $f^*$ is $\sigma^*$-uniformly convex. $\square$

Remark. If we only assume that $f$ is uniformly smooth on its domain, then it is not sufficient to guarantee the uniform convexity of $f^*$. A counter example in $\mathbb R^n$ is $f(x) = \frac{1}{2}||x||_2^2 + I(||x||_2\leq 1)$, then

$$f^*(x^*) = \begin{cases} \displaystyle \frac{1}{2}||x^*||_2^2 &, \quad ||x^*||_2\leq 1\\ \displaystyle ||x^*||_2-\frac{1}{2} &, \quad \text{otherwise.}\end{cases}$$

In this case, $f$ is $1$-strongly smooth on its domain, but $f^*$ contains linear part, thus not strictly/uniformly/strongly convex.

3. References

[1] Kakade, Sham, Shai Shalev-Shwartz, and Ambuj Tewari. “On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization.” (2009): 35.

[2] Zalinescu, C. “On uniformly convex functions.” Journal of Mathematical Analysis and Applications 95.2 (1983): 344-374.

[3] Zalinescu, Constantin. “Convex analysis in general vector spaces”. World scientific, 2002.