Convexity and Lipschitz continuity

Question

It is probably an easy question, but somehow I am stuck.

Question Is the following statement true? If yes, how to prove it?

Suppose that $f\in C^1(\mathbb{R}^n)$ is convex and $$ \langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L|x-y|^2 $$ for some $L>0$ and all $x,y\in\mathbb{R}^n$. Does it follow that $$ |\nabla f(x)-\nabla f(y)|\leq L|x-y| $$ for all $x,y\in\mathbb{R}^n$?

Answer 1

That's a standard result in convex optimization. For example Theorem 2.1.5 in Nesterov's "Introductory Lectures on Convex Optimization" states that the following are equivalent:

• $f$ is $C^1$, convex and the gradient $\nabla f$ is $L$-Lipschitz
• for all $x,y$: $0\leq f(y) - f(x) - \langle\nabla f(x),y-x\rangle \leq \tfrac{L}2 \|x-y\|^2$
• for all $x,y$: $\tfrac1L\|\nabla f(x)-\nabla f(y)\|^2 \leq \langle\nabla f(x)-\nabla f(y),x-y\rangle$
• for all $x,y$: $\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$

(In case you are interested: The proof there is directly for $C^1$ functions and no second derivatives are used at intermediate steps.)

Answer 2

Yes

Consider first the case where $f\in{\cal C}^2$. Then $$\nabla f(y)-\nabla f(x)=\int_0^1{\rm D}^2f(x+t(y-x))\cdot(y-x)\,dt.$$ There follows $$\|\nabla f(y)-\nabla f(x)\|\le\|y-x\|\int_0^1\|{\rm D}^2f(x+t(y-x))\|\,dt.$$ Now, the assumption tels you that $\|{\rm D}^2f(x+t(y-x))\|\le L$, whence the result.

Now the general case can be obtained by a density argument. Let a convex function $f$ satisfy your assumption. For $\epsilon>0$, et us define a smooth convex function $f_\epsilon$ by inf-convolution: $$f_\epsilon(x)=\inf_z(f(z)+\frac1\epsilon\,\|x-z\|^2).$$ Apply the result to $f_\epsilon$, then pass to the limit as $\epsilon\rightarrow0$.

Answer 3

This answer is a small modification of the answer of Denis Serre. I added for reader's convenience: (1) the result is slightly more general; (2) the answer contains much more details; (3) I am using a convolution by mollification approximation instead of inf-convolution.

Since convex functions satisfy $$ \langle \nabla f(x)-\nabla f(y),x-y\rangle\geq 0, $$ it suffices to prove the following more general result.

Theorem. Let $f\in C^1(\mathbb{R}^n)$ and let $L>0$.Then the following conditions are equivalent: \begin{equation} (1)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |\langle\nabla f(x)-\nabla f(y),x-y\rangle|\leq L|x-y|^2 \quad \text{for all $x,y\in\mathbb{R}^n$.} \end{equation} \begin{equation} (2)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |\nabla f(x)-\nabla f(y)|\leq L|x-y| \quad \text{for all $x,y\in\mathbb{R}^n$.} \end{equation}

Proof. While the implication (2) to (1) is obvious the other is not so we will prove the implication from (2) to (1) now. Assume first that $f\in C^\infty(\mathbb{R}^n)$. For $|u|=1$, (1) yields, $$ \left|\left\langle\frac{\nabla f(x+tu)-\nabla f(x)}{t},u\right\rangle\right|\leq L, $$ so passing to the limit as $t\to 0$ gives $$ |\langle D^2f(x)u,u\rangle|\leq L. $$ Since $D^2 f(x)$ is a symmetric matrix, the spectral theorem implies that the operator norm of the matrix $D^2f(x)$ satisfies $$ \Vert D^2f(x)\Vert = \sup_{|u|=1}|\langle D^2f(x)u,u\rangle|\leq L. $$ This estimate however, easily implies the result \begin{equation} \begin{split} & |\nabla f(x)-\nabla f(y)|= \left|\int_0^1\frac{d}{dt}\nabla f(y+t(x-y))\, dt\right|\\ &\leq |x-y|\int_0^1\Vert D^2f(y+t(x-y))\Vert\, dt\leq L|x-y|. \end{split} \end{equation} This completes the proof when$f\in C^\infty$. Assume now that $f\in C^1$ and let $f_\epsilon=f*\varphi_\epsilon$ be a standard approximation by convolution. Recall that $f_\epsilon\in C^\infty$ and $\nabla f_\epsilon=(\nabla f)*\varphi_\epsilon$. We have \begin{equation} \begin{split} & |\langle \nabla f_\epsilon(x)-\nabla f_\epsilon(y),x-y\rangle|= \Big|\Big\langle\int_{\mathbb{R}^n} (\nabla f(x-z)-\nabla f(y-z))\varphi_\epsilon(z)\, dz,x-y\Big\rangle\Big|\\ &\leq \int_{\mathbb{R}^n} \big|\big\langle \nabla f(x-z)-\nabla f(y-z)),(x-z)-(y-z)\big\rangle\big|\, \varphi_\epsilon(z)\, dz \leq L|x-y|^2, \end{split} \end{equation} where the last inequality is a consequence of (1) and $\int_{\mathbb{R}^n}\varphi_\epsilon=1$. Since $f_\epsilon\in C^\infty$, the first part of the proof yields $$ |\nabla f_\epsilon(x)-\nabla f_\epsilon(y)|\leq L|x-y| $$ and the result follows upon passing to the limit as $\epsilon\to 0$.

Answer 4

A partial answer: if you're willing to strengthen your assumption and suppose $f\in C^2(\mathbb{R}^n)$, then yes. Otherwise, I'm not sure.

---

Functions that satisfy - $$\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$$ are called "L-semi-concave", and functions that satisfy - $$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$$ are called "L-smooth".

If $f\in C^2(\mathbb{R}^n)$ is both at least L-semi-convex (in particular, convex) and at-least L-semi-convave - then it is indeed L-smooth.

One may prove it by considering the Hessian $\nabla^2f$ of $f$: the convexity implies it is positive semidefinite, and the semi-concavity implies that $\nabla^2f-\frac{1}{2}\mathrm{Id}$ is negative semidefinite. Therefore, the operator-norm of $\nabla^2f$ must be bounded, which means that $\nabla f$ is Lipschitz (i.e. $f$ is L-smooth).

I'm not sure if it still holds under the weaker assumption $f\in C^1(\mathbb{R}^n)$.