14
$\begingroup$

I've read in a few places that if we have a Lipschitz gradient

$$\|\nabla f(x) - \nabla f(y)\|\leq L\|x-y\|,\, \forall x,y, $$ we can equivalently say $\nabla^2f\preceq LI.$ But I'm having a hard time showing this. (Equivalently, I want to show $z^T \nabla^2f(x)z\leq z^TLIz=Lz^Tz,\forall\, x,z $.)

$\endgroup$
  • $\begingroup$ @user147263 I have a question regarding his answer, When you use mean value theorem. You will get something like: $$\|\nabla f(x)-\nabla f(y)\|\le \|\nabla^2 f \| \|x-y\|$$ From this have can you judge whether $\|\nabla^2 f \| \le L$ or not? The equality in the cauchy schwarz may not be obtained? $\endgroup$ – Li haonan Mar 17 '18 at 21:44
17
$\begingroup$

This is not true as stated. For example, the function $f(x)=x|x|$ on the real line has Lipschitz gradient, but is not twice differentiable. Also, the function $f(x)=-x^4$ satisfies $f''\le LI$ with $L=0$, but its gradient is not Lipschitz continuous.

The two properties are equivalent for functions that are convex and twice differentiable. For such functions, $\nabla^2 f$ is a positive semidefinite matrix, so its norm is its largest eigenvalue. Hence, $$\nabla^2 f \preceq LI \iff \|\nabla^2 f\|\le L \iff \|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|$$ where the last equivalence is based on the mean value theorem.

$\endgroup$
  • 1
    $\begingroup$ Are you sure that the Lipschitz constant is preserved in the equivalence, or there is some factor depending on the dimension $n$ ($f:\mathbb R^n\to \mathbb R$) ? Thanks. $\endgroup$ – Svetoslav Mar 15 '16 at 19:09
  • 1
    $\begingroup$ It's preserved. The mean value theorem is applied on the line passing through $x,y$, so the problem becomes one-dimensional. $\endgroup$ – user147263 Mar 15 '16 at 19:10
  • $\begingroup$ can you expand on how the the mean value theorem is applied here? $\endgroup$ – Sridhar Thiagarajan Aug 13 '18 at 8:46
  • $\begingroup$ @SridharThiagarajan The following link answers your question: math.stackexchange.com/questions/2294536/… $\endgroup$ – pikachuchameleon Jan 26 '19 at 15:56
0
$\begingroup$

It is equivalent for $||\bigtriangledown ^2f(x)||_2 \leq L$ where $||\bigtriangledown ^2f(x)||_2$ means the maximum singular value.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.