1
$\begingroup$

I know if a function $f: \mathbb{R}^n \to \mathbb{R}$ is $L$-smooth, i.e. its gradient $\nabla f$ is $L$-Lipschitz continuous, then it satisfies the following inequality for any $x, x_0 \in \mathbb{R}^n$: $$ \left| f(x) - \left( f(x_0) + \nabla f(x_0)^\top (x - x_0)\right) \right| \leq \frac{L}{2} \lVert x - x_0 \rVert_2^2 \text{.} $$

Here's my question: is the converse true? I know that, provided $f$ is convex, then we can conclude that $f$ satisfying the above inequality must be $L$-smooth. But what if $f$ is not necessarily convex? If the converse is false, can you give some counterexamples?

$\endgroup$
2
  • 1
    $\begingroup$ I don't know off the top of my head, but this post xingyuzhou.org/blog/notes/Lipschitz-gradient does explicitly say that this implication does not hold without convexity (but does not give a counterexample). $\endgroup$
    – Dirk
    Dec 20, 2022 at 16:04
  • 1
    $\begingroup$ @Dirk Still very helpful, thank you! $\endgroup$
    – aest
    Dec 20, 2022 at 17:29

1 Answer 1

1
$\begingroup$

Yes, the converse is also true. This follows from the answer in https://math.stackexchange.com/questions/4227159/characterization-of-lipschitz-derivative.

In fact, your condition yields $$ | (\nabla f(x_0) - \nabla f(x))^\top (x_0 - x) | \le L \| x_0 - x \|_2^2 $$ and the linked answer then gives the Lipschitzness of $\nabla f$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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