2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ did you find a proof? $\endgroup$ Aug 13, 2018 at 8:37

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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