On the Hessian 1: Classical Optimization

The Hessian’s Role in First-Order Convergence

Gradient descent motivates its rule through a local descent step via the first-order Taylor approximation of a function:

$$f(x+s)\approx f(x)+s^T\nabla f(x)$$

This provides a little more sophistication than most initial introductions to GD, which simply state that “the gradient points in the direction of greatest ascent, so move in the negative gradient direction”, since the Taylor approximation is local, and prevents us from assuming that arbitrarily choosing $s=-t\nabla f(x)$ and letting $t\to -\infty$. This is bad because the Taylor has those higher-order terms tucked in, that grow (at least linearly) with $||s|{|}_2$.

The locality requirement can be made explicit by requiring that we minimize the first-order Taylor within a norm-ball:

$$\underset{||s|{|}_2<\eta }{\min }f(x+s)$$

which translates to

$$\underset{||s|{|}_2<\eta }{\min }{s}^T\nabla f(x)$$

which, after an application of (the lower-bound of) Cauchy-Schwartz and controlling for equality, gives the steepest local descent step to be $s=-\eta \nabla \frac{f(x)}{||\nabla f(x)|{|}_2}$

While nowhere did we make explicit the Hessian of $f$, as would have been necessary if we were to instead start with the second-order expansion, the convergence of first-order methods is still governed by how “good” each gradient step is, which means knowing whether the choice of $\eta$ was sufficiently local. This means we still need to look at at least the second-order Taylor term.

The question now becomes “what Hessian structure permits what rate for a given first-order method?”

Function Classes as Hessian Structure

Before looking at the algorithms, let’s see what claims we can make about the Hessian for the canonical set of function classes that we see during convergence rate analysis.

L-Smooth Functions

A L-smooth function is one whose gradient is L-Lipschitz continuous ¹:

$$|\nabla f(x)-\nabla f(y)|\le L||x-y||$$

Proposition 1: L-smoothness as Hessian Ordering

A twice-differentiable function is L-smooth if and only if $-LI⪯{\nabla }^{2}f(x)⪯LI$

Before proving this, it’s worth stating and proving a few useful lemmas:

Lemma 1

For symmetric $H$, $-LI⪯H⪯LI⟹||Hd||\le L||d||$ for all vectors $d$.

Proof: While the use of operator norms makes this proof trivial, we can save on defining them by utilizing H’s eigendecomposition:

$$H=Q\Lambda Q^T$$

where $\Lambda =\text{diag}({\lambda }_1\dots {\lambda }_n)$. Setting $Q^{T}d=a$, we get

$$||Hd|{|}^2=d^{T}HHd=(Q^{T}d{)}^T{\Lambda }^2{Q}^{T}d=a^T{\Lambda }^{2}a=\sum _{i=1}^n{\lambda }_i^2{a}_i^2\le L^2\sum _{i=1}^n{a}_i^2=L^2||a|{|}^2=L^2||d|{|}^2$$

Where we used the fact that the Loewner bounds on $H$ imply that ${\lambda }_{\text{max}}(H)\le L$ ².

Lemma 2: The Fundamental Theorem of Calculus

For $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$, let $x,y\in {\mathbb{R}}^n$ and $r=y-x$. Then

$$f(y)-f(x)={\int }_0^{1}J(f(x+tr))rdt$$

Where $J(f(x))$ is the Jacobian of $f$. When applied to gradients, this becomes

$$\nabla f(y)-\nabla f(x)={\int }_0^1{\nabla }^{2}f(x+tr)rdt$$

Proof of Proposition 1
Direction 1: L-smoothness implies Hessian bound:
Setting $x=z$ and $y=z+tv$ for direction $v$, we get

$$\begin{array}{rl}||\nabla f(z+tv)-\nabla f(x)||& \le L|t|\cdot ||v||\\ ⟹||\frac{\nabla f(z+tv)-\nabla f(x)}{t}||& \le L||v||\end{array}$$

Letting $t\to 0$, we get that the term within the norm on the LHS to be the directional derivative in the direction of $v$, namely ${\nabla }^{2}f(x)v$.
Therefore, we have

$$||{\nabla }^{2}f(x)v||\le L||v||$$

With Cauchy-Schwartz:

$$|v^T{\nabla }^{2}f(x)v|\le ||v||\cdot ||{\nabla }^{2}f(x)v||\le L||v|{|}^2$$

Since the choice of $v$, was arbitrary, we have that $-L||v|{|}^2\le v^T{\nabla }^{2}f(x)v\le L||v|{|}^2$ for all $v$, and thus that $-LI⪯{\nabla }^{2}f(x)⪯LI$.

Direction 2: Hessian bound implies L-smoothness:
Applying Lemma 2 to the gradients, we have

$$||\nabla f(y)-\nabla f(x)||=||{\int }_0^1{\nabla }^{2}f(x+tr)rdt||\le {\int }_0^1||{\nabla }^{2}f(x+tr)r||dt$$

Applying Lemma 1 to the integrand, we get

$$||\nabla f(y)-\nabla f(x)||\le {\int }_0^{1}L||r||dt=L||r||=L||y-x||$$

Thus, we can now claim that, if a twice-differentiable function has ${\lambda }_{\text{max}}({\nabla }^{2}f(x))\le L$, then it is L-smooth.

Convex Functions

A function is convex over a convex set $C$ if for every $x,y$ in $C$,

$$f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$$

where $t\in [0,1]$

For convex functions, we have the following

Proposition 2: Convexity as Hessian Positive Semi-Definiteness

A function $f$ is convex if and only if its Hessian is PSD, i.e. ${\nabla }^{2}f(x)⪰0$

The proof of this statement can be found here. Thus, we see that while smoothness supplies us with an upper-bound on the curvature, convexity gives us a lower-bound.

$\mu -$Strongly Convex Functions

A function is $\mu -$strongly convex if

Footnotes

1. Smoothness can be defined for any norm, but I will assume everywhere the ${\ell }_2$ norm unless otherwise specified ↩

2. This can be seen by using the fact that $-L||v|{|}^2\le v^{T}Hv\le L||v|{|}^2$, and setting $v$ to be the eigenvector corresponding to ${\lambda }_{\text{max}}(H)$ ↩