Suppose $f: \mathbb{R}^n \rightarrow \mathbb{R}$ and is a $C^1$, i.e., $\nabla f $ is a continuous vector valued function.

Show if the $\lambda_{max}$ of $\nabla^2f$ is bounded, then $\nabla f$ is Lipshitz with global constant $\lambda_{max}$.

Proof: $$ \nabla f(y) - \nabla f(x) =\int_0^1 \nabla^2f (x+t(y-x))(y-x)dt \,\,\,\, \forall x,y \in \mathbb{R}^n $$ $$ \|\nabla f(y) - \nabla f(x) \|=\|\int_0^1 \nabla^2f (x+t(y-x))(y-x)dt \|\,\,\,\, \forall x,y \in \mathbb{R}^n $$

Using Cauchy-Schwarz we have

$$ \|\nabla f(y) - \nabla f(x) \| \leq \int_0^1 \|\nabla^2f (x+t(y-x))\|\|(y-x)\|dt \,\,\,\, \forall x,y \in \mathbb{R}^n $$

$$ \|\nabla f(y) - \nabla f(x) \| \leq \lambda_{max}(\nabla^2f)\|(y-x)\|dt \,\,\,\, \forall x,y \in \mathbb{R}^n $$

What is the intuition behind this claim? Please discuss this from different point of views, for example curvature, function behaviour, ... .


The following is an imprecise wording of the situation (since you are asking for intuition), but can be made mathematically precise.

For univariate functions $\mathbb{R} \to \mathbb{R}$, this states that a bound on [the absolute value of] the second derivative (curvature) implies the derivative (slope) cannot change too quickly (Lipschitz).

In general for functions $\mathbb{R}^n \to \mathbb{R}$, the Hessian captures curvature information in multiple directions, and the maximum eigenvalue is the maximum curvature. If this quantity is bounded, it bounds curvature in all directions, and thus implies the gradient ("slope") cannot change too quickly (Lipschitz).

| cite | improve this answer | |
  • $\begingroup$ What do we mean when we say curvature is bounded, intuitively? I can think of $y=ax^2$ for large $a$, and say in higher dimension that means we have no narrow deep valleys provided bounded curvature. Is that right? $\endgroup$ – Saeed May 11 '19 at 19:54

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.