I can find a ton of examples on this site of functions that are smooth but not (globally) Lipschitz, but I can't seem to find the reverse direction. For reference, I'm trying to "solve" Exercise 7.2 from Vishnoi's Algorithms for Convex Optimization:
Give an example of a function $f : \mathbb{R}^n \to \mathbb{R}$ such that $\| \nabla f(x) \|_2 \le 1$ for all $x \in \mathbb{R}^n$ but the Lipschitz constant of its gradient is unbounded.
(This is not assigned homework. I'm reading this textbook purely out of personal interest.)
My approach:
I'm fine with understanding the spirit of the solution rather than nailing it exactly, so I'm okay with simplifying the problem as stated. Thus, I'm confining myself to functions $f : \mathbb{R} \to \mathbb{R}$. (But I still might write the gradient instead of just the derivative just because I'm referencing the textbook.)
Recall that the condition $\| \nabla f(x) \|_2 \le 1$ implies $1$-Lipschitzness, i.e.,
$$
|f(x) – f(y)| \le \| x – y\|_2.
$$
(Hence the title, since I figure it is more searchable.) For convex functions, the two conditions are equivalent.
Saying the gradient is $L$-Lipschitz is equivalent to saying $f$ is $L$-smooth. Again, hence the title, since it is more searchable.
So intuitively, we are looking for a function $f : \mathbb{R} \to \mathbb{R}$ whose derivative is bounded by a constant ($1$ to be exact, but let's just say a constant). But it needs to have an unbounded second derivative. (Using the fact that saying the gradient is $L$-Lipschitz is equivalent to an upper bound on the gradient of the gradient.)
In other words, we want a function that doesn't change very fast but has unbounded curvature. I'm been looking at random functions that come to mind, but I'm struggling. Any help would be greatly appreciated. Thanks!
Best Answer
Maybe the following is easier: Find a function $g \colon \mathbb R \to \mathbb R$ such that $|g| \le 1$, but $g$ fails to be Lipschitz continuous.
Then, you can set $\nabla f = g$.