9
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much. Since it is too long, I will split it into two comments: (1) My understanding is that you used the following argument: by passing to the limit with difference quotient, the condition that I have implies $\langle D^2f(x)u,u\rangle\leq L$ for any $|u|=1$ and hence $|\langle D^2f(x)u,u\rangle|\leq L$, because convexity implies $D^2f(x)\geq 0$. Then the spectral theorem for symmetric matrices yields $\Vert D^2f(x)\Vert=\sup_{|u|=1}|\langle D^2f(x)u,u\rangle|\leq L$. Here, $\Vert D^2f(x)\Vert$ is the operator norm. $\endgroup$ – Piotr Hajlasz Oct 24 at 13:02
  • $\begingroup$ (2) I think the inf-convolution is only $C^{1,1}$ and this is not an obvious fact. While your argument works for $C^{1,1}$ functions, it is delicate in that case as $D^2f$ exists a.e. only. I think it is much easier to use approximation by standard mollification. Please, let me know if both of my comments make sense. $\endgroup$ – Piotr Hajlasz Oct 24 at 13:02
  • $\begingroup$ @PiotrHajlasz. Yes, your comments do make sense. 1st one : you correctly point out that the symmetry of the Hessian is an important ingredient. $\endgroup$ – Denis Serre Oct 24 at 13:42
  • $\begingroup$ @PiotrHajlasz. Your 2nd comment. Well, I am not familiar with inf-convolution. But there are other ways to regularize a convex function. One of them is to consider its Legendre transform, then to add $\epsilon\rho$ where $\rho$ is smooth convex with $\nabla\rho$ bounded, then to transform back. $\endgroup$ – Denis Serre Oct 24 at 13:45
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ If you approximate a $C^1$, convex, "L-semiconcave" function $f$ by convolution with a smooth nonnegative kernel, you get a sequence of smooth convex L-semiconcave functions converging $C^1$ to $f$, so the smooth case is sufficient. $\endgroup$ – Pietro Majer Oct 24 at 7:46
  • $\begingroup$ Thank you, but could you add references? Without any references the answer is not useful since the facts that you mentioned are not obvious. $\endgroup$ – Piotr Hajlasz Oct 24 at 10: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.