# Strong convexity/Lipschitz gradient duality for convex conjugates and strong convexity/Lipschitz gradient criteria

If $$f : \mathbb R^n \to \mathbb R$$ is $$C^2$$ and convex, I want to show that $$f$$ has a $$L$$-Lipschitz gradient if and only if its convex conjugate $$f^*$$ is $$\frac{1}{L}$$ strongly convex.

I received a hint to consider using the fact that $$f(x) \leq g(x)$$ for all $$x$$ implies $$f^*(x) \geq g^*(x)$$ and try to upper bound $$f(x)$$, and I reached the conclusion that $$f^*(x) \geq \langle x, y \rangle - f(y) + \frac{1}{2 L} || x - \nabla f(y) ||_2^2$$ for any $$x, y \in \mathbb R^n$$, but I am not sure how to show $$f^*(x) \geq f^*(y) + \nabla f^*(y) \cdot (x - y) + \frac{1}{2 L} || x - y||_2^2$$ from here.

Is there any way to go from what I have to the conclusion I'd like to reach? Also, for the other direction, what other approach would I need to consider?

Here is a proof of ($$\Leftarrow$$). We first prove an equivalent characterization of strong convexity:

$$\textbf{Lemma}$$: Let $$f$$ be a $$C^{1}$$ strongly convex function with parameter $$m > 0$$. The following statements are equivalent:

(i) $$f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle + \frac{m}{2}||y - x||_{2}^{2} \text{ }$$ for all $$x, y \in \text{dom}(f)$$.

(ii) $$g(x) = f(x) - \frac{m}{2}||x||_{2}^{2}$$ is convex for all $$x, y \in \text{dom}(f)$$.

(iii) $$\langle \nabla f(x) - \nabla f(y), x - y\rangle \geq m||x - y||_{2}^{2}$$ for all $$x, y \in \text{dom}(f)$$. (We will use (iii) in our proof of your problem).

$$\textbf{Proof of Lemma}$$:

First note that for $$x, y \in \text{dom}(f)$$:

$$\nabla g(x) = \nabla f(x) - mx \Rightarrow \nabla g(x) - \nabla g(y) = \nabla f(x) - \nabla f(y) + m(y - x)$$

(i) $$\Leftrightarrow$$ (ii): Let $$x, y \in \text{dom}(f)$$. By the first order characterization of convexity:

$$g(y) \geq g(x) + \langle \nabla g(x), y - x\rangle \Leftrightarrow f(y) - \frac{m}{2}||y||_{2}^{2} \geq f(x) - \frac{m}{2}||x||_{2}^{2} + \langle \nabla f(x) - mx, y - x\rangle$$

$$\Leftrightarrow f(y) \geq f(x) + \langle \nabla f(x), y - x\rangle + \frac{m}{2}(||x||_{2}^{2} - 2\langle x, y \rangle + ||y||_{2}^{2}) = f(x) + \langle \nabla f(x), y - x\rangle + \frac{m}{2}||y - x||_{2}^{2}$$

(ii) $$\Leftrightarrow$$ (iii): Let $$x, y \in \text{dom}(f)$$. Then by how a $$C^{1}$$ function is convex if and only if its gradient is monotone, $$g$$ is convex if and only if:

$$0 \leq \langle g(x) - g(y) , x - y \rangle = \langle (\nabla f(x) - \nabla f(y)) + m(y - x), x - y \rangle = \langle \nabla f(x) - \nabla f(y), x - y \rangle - m||x - y||_{2}^{2}$$

$$\Leftrightarrow \langle \nabla f(x) - \nabla f(y), x - y \rangle \geq m||x - y||_{2}^{2}$$

$$\textbf{End of Proof of Lemma}$$

Now, onto the problem you posed:

($$\Leftarrow$$) Since $$f$$ is $$C^{2}$$, by the Fenchel-Moreau theorem, we have $$f^{**} = f$$. Thus, the ($$\Leftarrow$$) is equivalent to showing if $$f$$ is $$\frac{1}{L}$$-strongly convex, then $$f^{*}$$ has a $$L$$-Lipschitz gradient. Recall that $$f^{*}(y) = \sup_{x \in \mathbb{R}^{n}}(\langle y, x \rangle - f(x))$$. Since $$f$$ is strongly convex, $$x \mapsto \langle y, x \rangle - f(x)$$ is strongly concave. Thus, the function has a maximizer and since every strongly convex function is strictly convex, the maximizer is unique. By first-order condition:

$$0 = \nabla_{x}(\langle y, x \rangle - f(x)) = y - \nabla f(x) \Rightarrow \nabla f(x^{*}) = y \Rightarrow x^{*} = g(y)\text{, for some invertible }g \in {C}^{1}(\mathbb{R}^{n}, \mathbb{R}^{n})$$ $$\Rightarrow f^{*}(y) = \langle y, g(y)\rangle - f(g(y))$$

By the chain rule,

$$\nabla f^{*}(y) = g(y) + (D_{y}g(y))^{T}y - (D_{y}g(y))^{T}\nabla_{x}f(g(y)) = g(y) + (D_{y}g(y))^{T}(y - \nabla_{x}f(x^{*})) = g(y) = x^{*}$$

where $$D_{y}g = (\frac{\partial g_{i}}{\partial y_{j}})_{i,j = 1}^{n}$$ is the Jacobian matrix.

Let $$y_{1}, y_{2} \in \mathbb{R}^{n}$$ and $$x_{i}^{*} = \text{argmax}_{x \in \mathbb{R}^{n}}(\langle y_{i}, x \rangle - f(x)) = g(y_{i})$$ for $$i = 1, 2$$. By strong convexity ((iii) in the lemma),

$$\frac{1}{L}||\nabla f^{*}(y_{1}) - \nabla f^{*}(y_{2})||_{2}^{2} = \frac{1}{L}||x_{1}^{*} - x_{2}^{*}||_{2}^{2} \leq \langle \nabla f(x_{1}^{*}) - \nabla f(x_{2}^{*}), x_{1}^{*} - x_{2}^{*} \rangle$$ $$= \langle y_{1} - y_{2}, g(y_{1}) - g(y_{2}) \rangle \leq ||y_{1} - y_{2}||_{2}||g(y_{1}) - g(y_{2})||_{2}\text{, by Cauchy-Schwarz}$$

$$\leq \text{sup}_{y \in \mathbb{R}^{n}}||D_{y}g||_{2}||y_{1} - y_{2}||_{2}^{2}\text{, where for }A \in \mathbb{R}^{n \times n}, ||A||_{2} = \text{inf}\{M > 0\text{ | } ||Ax||_{2} \leq M||x||_{2} \forall x \in \mathbb{R}^{n} \}$$

Note that for $$x^{*} = \text{argmax}_{x \in \mathbb{R}^{n}}(\langle y, x \rangle - f(x)) = g(y)$$, we have by the chain rule:

$$y = \nabla f(x^{*}) = \nabla f(g(y)) \Rightarrow I_{n} = D_{y}(\nabla f \circ g)(y) = \nabla^{2}_{x}f(g(y))D_{y}g(y) = \nabla^{2}_{x}f(x^{*})D_{y}g(y)$$ $$\Rightarrow D_{y}g(y) = (\nabla^{2}_{x}f(x^{*}))^{-1}$$

Note that $$\nabla^{2}_{x}f(x^{*})$$ is invertible because by the second-order characterization of $$\frac{1}{L}$$-strong convexity, we have $$\nabla^{2}_{x}f(x^{*}) \succcurlyeq \frac{1}{L}I_{n}$$, implying all (real) eigenvalues of $$\nabla^{2}_{x}f(x^{*})$$ are positive and thus $$\text{det}(\nabla^{2}_{x}f(x^{*})) \neq 0$$. Also, we have $$\nabla^{2}_{x}f(x^{*}) \succcurlyeq \frac{1}{L}I_{n} \Rightarrow LI_{n} \succcurlyeq (\nabla^{2}_{x}f(x^{*}))^{-1}$$. Thus,

$$\frac{1}{L}||\nabla f^{*}(y_{1}) - \nabla f^{*}(y_{2})||_{2}^{2} \leq \text{sup}_{x^{*} \in \mathbb{R}^{n}}||(\nabla_{x}^{2}f(x^{*}))^{-1}||_{2}||y_{1} - y_{2}||_{2}^{2}$$ $$\leq L||y_{1} - y_{2}||_{2}^{2}$$ $$\Rightarrow ||\nabla f^{*}(y_{1}) - \nabla f^{*}(y_{2})||_{2} \leq L||y_{1} - y_{2}||_{2}$$

which is what we want. To see why $$||(\nabla^{2}_{x}f(x^{*}))^{-1}||_{2} \leq L$$ above, note that:

$$||(\nabla^{2}_{x}f(x^{*}))^{-1}||_{2} = \sqrt{\lambda_{\text{max}}(((\nabla^{2}_{x}f(x^{*}))^{-1})^{T}(\nabla^{2}_{x}f(x^{*}))^{-1})}$$ $$= \sqrt{\lambda_{\text{max}}(((\nabla^{2}_{x}f(x^{*}))^{-1})^{2})}\text{, by equality of mixed partials}$$ $$= \lambda_{\text{max}}((\nabla^{2}_{x}f(x^{*}))^{-1}) \leq L$$