# Does Lipschitz-continuous gradient imply that the Hessian is bounded in spectral norm by the same Lipschitz constant?

The present question is in reference to the question Lipschitz-constant gradient implies bounded eigenvalues on Hessian

If $$f: \mathbb{R^n} \to \mathbb{R}$$ is a twice differentiable function satisfying $$\| \nabla f(x) - \nabla f(y) \|_2 \leq L \|x-y\|_2 , \quad \forall x,y \in \mathbb{R}^n$$ then is the following also true? $$\| \nabla^2 f(x) \|_2 \leq L, \quad \forall x ?$$ where the last norm refers to the maximum singular value norm.

There is a counterexample provided in one of the answers here: Lipschitz-constant gradient implies bounded eigenvalues on Hessian but this is not really a counterexample, since $$f$$ is not twice differentiable in that example. Can anyone be kind enough to prove or disprove the statement assuming that $$f$$ is twice differentiable? Note that, I am not assuming that $$f$$ is convex.

• did you find a proof? Aug 13, 2018 at 8:37

It is true:

Recall an important property of Lipschitz-constant gradient:

$$g(x) = \frac{L}{2}x^\top x-f(x)$$ is convex.

Thus, due to the second order condition of convexity, we have:

$$0 \preceq \nabla^2 g(x) = L - \nabla^2f(x)$$.

Then,

$$\nabla^2f(x)\preceq L$$, implying $$\lambda_\max (\nabla^2f(x))\leq L$$.

Since the norm is the maximum singular value norm, we obtain the result.