0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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 $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .