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?

Improve this question
$\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
    Commented Dec 20, 2022 at 16:04
  • 1
    $\begingroup$ @Dirk Still very helpful, thank you! $\endgroup$
    – aest
    Commented Dec 20, 2022 at 17:29

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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