16
$\begingroup$

I'm working with the following two concepts:

  • Lipschitz Smoothness - a function $f$ is Lipschitz smooth with constant $L$ if its derivatives are Lipschitz continuous with constant $L$, in other words if for any $x$ and $y$, $$ \| \nabla f(x) - \nabla f(y) \| \leq L \| x - y \| $$
  • Strong Convexity - a function $f$ is $\alpha$-strongly convex if $$ \nabla^2 f(x) \succeq \alpha I $$ for all $x$, where $I$ is the identity matrix.

Here are my questions:

  1. I know that Lipschitz Smoothness implies that for any $x$ and $y$, it is true that $$ f(x + y) \leq f(x) + y^\top \nabla f(x) + \frac{L}{2} \| y \|^2 $$ Is the converse also true? ie: is it an "if and only if"?
  2. I read somewhere that $f$ is Lipschitz smooth if and only if $$ L I \succeq \nabla^2 f(x) $$ for all $x$, where $I$ is the identity matrix. How can I prove that?
  3. I read somewhere that $f$ is $\alpha$-strongly convex if and only if for any $x$ and $y$, it is true that $$ f(x+y) \leq f(x) + y^\top\nabla f(x) - \frac{\alpha}{2} \| x - y \| $$ How can I prove this, and is it and if-and-only-if?
  4. The previous two points seem to imply some relationship between these two concepts. Does it go any deeper?

I realize this is a bunch of questions - if anyone has a good reference on these topics, that'd be swell too...

Thanks

$\endgroup$
  • $\begingroup$ Welcome to MSE! If you break this into several questions, perhaps with links between the different questions you will make it easier for others to respond. Some people may be able to answer one question but not another. $\endgroup$ – Jay Feb 12 '14 at 16:02
5
$\begingroup$

I assume that your question concerns convex functions only; without convexity much of it would be false.

Question 2: strictly speaking, being Lipschitz smooth ($C^{1,1}$) does not imply $\nabla^2 f$ exists. But the statement is true if we interpret $\nabla^2 f\preceq LI$ as holding almost everywhere. Indeed, $\nabla^2 f$ is a positive semidefinite matrix, so having $\nabla^2 f\preceq LI$ a.e. is equivalent to $\nabla^2 f\in L^\infty$. And it is well known that having $L^\infty$ derivative is equivalent to being Lipschitz; thus $$\nabla^2 f\in L^\infty \iff \nabla f\in C^{0,1} \iff f\in C^{1,1}$$

Question 3: You misremembered. The correct inequality characterizing $\alpha$-strong convexity is $$f(x+y) \ge f(x) + y^\top\nabla f(x) + \frac{\alpha}{2} \| x - y \|^2 \tag{1}$$ Indeed, (1) is equivalent to saying that the function $g(x)=f(x)-\frac{\alpha}{2} \| x \|^2$ is convex. The latter is equivalent to $\nabla^2 g\succeq 0$, which is $\nabla^2 f\succeq \alpha\, I$.

Question 4. Yes, there is a direct and important relation: a function is strongly convex if and only if its convex conjugate (a.k.a. Legendre-Fenchel transform) is Lipschitz smooth. Indeed, the gradients maps are inverses of each other, which implies that the Hessian of convex conjugate of $f$ is the inverse of the Hessian of $f$ (at an appropriate point). So, a uniform upper bound on $\nabla^2 f$ is equivalent to a uniform lower bound on $\nabla^2 (f^{*}) $, and vice versa. One can also argue without referring to the Hessian (which may fail to exist at some points): the Lipschitz smoothness of $f$, by your item 1, gives us at every $x_0$ a quadratic function $q$ so that $q(x_0)=f(x_0)$ and $f \le q$ everywhere. Taking convex conjugate reverses the order: $q^*\le f^*$; and this means that $f^*$ is strongly convex.

Question 1. The converse is true, but the only proof I see goes through the convex conjugate as described in Q4. Since strong convexity is characterized by the comparison property (1), taking the conjugate gives a matching characterization of Lipschitz smoothness.

Reference: Chapter 5 of Convex functions by Jonathan M. Borwein and Jon D. Vanderwerff.

$\endgroup$
  • $\begingroup$ How can you use $\nabla^2 f\preceq LI$ to prove the same thing i.e. to prove $\nabla^2 f\preceq LI$ in question 2? Please elaborate the proof. $\endgroup$ – chandresh Jul 9 '15 at 12:09
  • $\begingroup$ The relation between gradient maps of $f$ and $f^*$ is only double-sided for convex functions. What can you say about $\partial f$ from $\partial f^*$ in general? You can definitely say that $f^{**}$ is strongly convex if and only if $f^*$ is Lipschitz smooth. $\endgroup$ – Arash Aug 15 '19 at 7:46

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.