Lipschitz continuous gradient and quadratic bound property

1k Views Asked by At

Let $\left\lVert \cdot \right\rVert$ denote the Euclidean norm. A differentiable function $f: D \subseteq \mathbb{R}^n \to \mathbb{R}$ is said to have Lipschitz continuous gradient with parameter $L > 0$ if $$ \left\lVert \nabla f(x) - \nabla f(y) \right\rVert \leq L \left\lVert x-y \right\rVert \text{for all } x, y \in D. \tag{1}\label{1}$$ A standard result is that a function $f$ (not necessarily convex) with Lipschitz continuous gradient satisfies the following "quadratic bound property": $$|f(y) - f(x) - \nabla f(x)^T(y-x)| \leq \frac{L}{2} \left\lVert x - y \right\rVert^2 \text{ for all } x, y \in D. \tag{2}\label{2}$$

I am thinking about the converse, namely if a function $f$ satisfies \eqref{2}, does it necessarily satisfy \eqref{1}? In http://www.seas.ucla.edu/~vandenbe/236C/lectures/gradient.pdf (slide 17) it seems like if we for instance assume that $f$ is convex with co-coercive gradient, the quadratic bound property implies Lipschitz continuity of the gradient. However, without these assumptions I strongly suspect that \eqref{2} does not necessarily imply \eqref{1}.

Just for fun, I have (without success) been trying to come up with an example of a function satisfying \eqref{2} but not \eqref{1}. Can anyone provide an example of such a function, or motivate why it does not exist?