2
$\begingroup$

I am studying Mirror descent and nonlinear projected subgradient methods. At page 170 proposition 3.1, part d, the author claims that $\phi^*$ is finite and differentiable if and only if the inverse map $(\partial \phi)^{-1}$ is everywhere single valued and Lipschitz continuous with $\sigma^{-1}$ where $\phi {}:{} \mathbb{R}^n \rightarrow \mathbb{R} \cup \{+\infty\}$ be a proper convex and Lipschitz function and $\sigma >0$.

Show $\phi^*$ is finite and differentiable if and only if the inverse map $(\partial \phi)^{-1}$ is everywhere single valued and Lipschitz continuous with $\sigma^{-1}$.

$\phi^*$ is conjugate function which is defined as below: $$ \phi^*(z) = \sup_x {}\{ \langle x,z\rangle - \phi(x)\}. $$

$\endgroup$
  • $\begingroup$ They cite the book of Rockafellar and Wets. Do you have access to that? $\endgroup$ – Pantelis Sopasakis May 14 at 16:38
  • $\begingroup$ @Pantelis Sopasakis: I do but I wanted to have the proof in simple wording here. $\endgroup$ – Saeed May 14 at 23:36
1
$\begingroup$

Firstly, $\sigma$ is not the Lipschitz constant of $\phi$. It is the strong convexity modulus of $\phi$, if $\phi$ is assumed to be strongly convex.

If $\phi^*$ is finite everywhere and differentiable, its subdifferential,

$$ \partial \phi^*(x) = \{\nabla \phi^*(x)\} $$

for all $x$. But $v\in \partial \phi(x)$ is equivalent to $x \in \partial \phi^*(v)$ (since $\phi$ is assumed to be proper, convex and lsc). Therefore, $\partial \phi^* = (\partial \phi)^{-1}$, which is single-valued.

Conversely, we want to prove that if $(\partial \phi)^{-1}$ is everywhere single-valued, then $\phi^*$ is everywhere finite and differentiable. To that end we use the fact that $\phi = \phi^{**}$ (because $\phi$ is assumed to be proper and lsc) and we apply what we showed above.

The rest of your question has to do with the Lipschitz constant of $(\partial \phi)^{-1}$ being $1/\sigma$ when $\phi$ is $\sigma$-strongly convex. By definition, $\phi$ is $\sigma$-strongly convex if $\phi-\tfrac{\sigma}{2}\|{}\cdot{}\|^2$ is convex. It is easy to show that $\phi$ is strongly convex if and only if $\partial \phi$ is strongly monotone. Then, we apply Proposition 12.54 in the book of Rockafellar and Wets to complete the proof.

$\endgroup$
  • $\begingroup$ Could you explain why $v \in \partial \phi(x)$ is equivalent to $x\in \partial \phi^*(v)$? What fact you are using to get this? I would appreciate if show me how you get this using the definition. $\endgroup$ – Saeed May 15 at 18:20
  • $\begingroup$ @Saeed I will update my answer later tonight or tomorrow. If you have access to Rockafellar's "Convex Analysis" you can find this in Chapter 23. $\endgroup$ – Pantelis Sopasakis May 15 at 18:28
  • $\begingroup$ I will appreciate if you update your answer. $\endgroup$ – Saeed May 15 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.