21
$\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$
1
  • $\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, 2018 at 21:44

3 Answers 3

23
$\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$
5
  • 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, 2016 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, 2016 at 19:10
  • 1
    $\begingroup$ can you expand on how the the mean value theorem is applied here? $\endgroup$ Aug 13, 2018 at 8:46
  • $\begingroup$ @SridharThiagarajan The following link answers your question: math.stackexchange.com/questions/2294536/… $\endgroup$ Jan 26, 2019 at 15:56
  • $\begingroup$ Why using convexity? Even if $\nabla^2 f$ is indefinite, as long as it is symmetric (which is guaranteed if $f$ is twice Frechet differentiable or simply $C^2$), the norm is its largest eigenvalue. $\endgroup$
    – William
    Apr 25, 2022 at 21:28
3
$\begingroup$

Implication from gradient to Hessian holds true for a twice differentiable function. From the definition of the Hessian of a twice differentiable function $f(\mathbf{x})$, we know that for any vector $\mathbf{v}\in\mathcal{R}^n$

\begin{align} \nabla^2f(\mathbf{x})\mathbf{v}&=\lim_{h\to0}\frac{\nabla f(\mathbf{x}+h\mathbf{v})-\nabla f(\mathbf{x})}{h}\\ \implies ||\nabla^2f(\mathbf{x})\mathbf{v}||&\leq\lim_{h\to0}\frac{||\nabla f(\mathbf{x}+h\mathbf{v})-\nabla f(\mathbf{x})||}{|h|}\\ \implies ||\nabla^2f(\mathbf{x})\mathbf{v}||&\leq\lim_{h\to0}L\frac{|h|||\mathbf{v}||}{|h|}\\ \implies ||\nabla^2f(\mathbf{x})\mathbf{v}||&\leq L||\mathbf{v}|| \end{align}

Since this is true for any $\mathbf{v}$, it is also true for the eigenvectors for matrix $\nabla^2f(\mathbf{x})$. If $\mathbf{v}$ is such an eigenvector \begin{align} ||\nabla^2f(\mathbf{x})\mathbf{v}||&=||\lambda\mathbf{v}||\leq L ||\mathbf{v}||\\ \implies |\lambda|\leq L \end{align}

So all eigenvalues are upper bounded by $L$

$\endgroup$
1
  • 2
    $\begingroup$ Please do not post the same answer twice. If you believe that one answer is suitable for more than one question, please answer one question, and flag the others as duplicates. $\endgroup$
    – Xander Henderson
    Nov 16, 2021 at 23:10
-1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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