1
$\begingroup$

A function is Lipschitz with constant $L$ if $\forall x,y \in \mathbb{R}^d$ it satisfies

\begin{equation} \|f(x)-f(y)\| \leq L\|x-y\| \end{equation}

A function is $L$-smooth if $\forall x,y \in \mathbb{R}^d$ it satisfies

\begin{equation} \|\nabla f(x) - \nabla f(y)\| \leq L\|x-y\| \end{equation}

My question is, does the first equation automatically imply the second?


I know that if a function is Lipschitz, then its gradients are bounded everywhere. To see this, rearrange the first equation:

\begin{equation} \frac{\|f(x) - f(y)\|}{\|x-y\|} \leq L \end{equation}

Then define $h=x-y$ and take the limit,

\begin{equation} \lim_{h \to 0} \frac{\|f(y+h) - f(y)\|}{\|h\|} = \|\nabla f(y)\| \leq L \end{equation}

This implies the following bound on $f(y)$:

\begin{equation} f(y) \leq f(x) + L\|y-x\| \end{equation}

I also know that $L$-smooth implies the following bound:

\begin{equation} f(y) \leq f(x) + \nabla f(x)^\top (y-x) + \frac{L}{2}\|y-x\|^2 \end{equation}

These last two equations look similar. In particular, $\frac{L}{2}\|y-x\|^2 \geq 0$, so I can add it to the first bound and get a true statement:

\begin{equation} f(y) \leq f(x) + L \|y-x\| + \frac{L}{2}\|y-x\|^2 \end{equation}

And now this looks very similar to the second bound. Am I right to think there's a connection here? Does Lipschitz continuity always imply $L$-smooth?

$\endgroup$
1
  • 2
    $\begingroup$ Lipschitz continuity does not even imply existence of derivative. Example, $f(x)=|x|$. $\endgroup$ Commented Feb 6, 2020 at 5:21

1 Answer 1

1
$\begingroup$

If $d = 1$ then a weaker version of your question is whether $f$ Lipschitz implies $f'$ Lipschitz. For a counterexample, take $f(x) = \int_0^x g(t)dt$ for any bounded function $g$ with unbounded derivative. Then $f' = g$ is bounded, so $f$ is Lipschitz, but $f'$ is not Lipschitz since $f'' = g'$ is unbounded. In fact the converse is not true either: $f'$ Lipschitz need not imply $f$ Lipschitz. For instance, take $f(x) = x^2$.

$\endgroup$

You must log in to answer this question.

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