First-order conditions tell us whether a point is a stationary point. But gradients only capture the "slope" of a function—they tell us nothing about the curvature. Are we at the bottom of a narrow valley or a wide basin? Is the function curving upward (convex) or downward (concave)? How quickly do gradients change as we move?

Second-order conditions answer these questions using the Hessian matrix—the matrix of second partial derivatives. This curvature information is fundamental to:

• Classifying critical points: Distinguishing minima from maxima and saddle points
• Verifying convexity: Confirming a function is globally bowl-shaped
• Algorithm design: Newton's method uses curvature for faster convergence
• Conditioning analysis: Understanding why some problems are hard to optimize

This page develops the mathematical theory of second-order conditions, from the basic definitions to their applications in machine learning optimization.

For a twice-differentiable function $f: \mathbb{R}^n \rightarrow \mathbb{R}$, the Hessian matrix $\nabla^2 f(x)$ (or $H_f(x)$) is the $n \times n$ matrix of second partial derivatives:

$$(\nabla^2 f(x))_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}(x)$$

Explicitly:

$$\nabla^2 f(x) = \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \ \vdots & \vdots & \ddots & \vdots \ \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{pmatrix}$$

Interpretation: Local Curvature

The Hessian captures how the gradient changes as we move through space:

$$\nabla f(x + \Delta x) \approx \nabla f(x) + \nabla^2 f(x) \Delta x$$

If we move in direction $v$, the rate of change of the gradient in direction $v$ is:

$$v^T \nabla^2 f(x) v$$

This quantity is the directional second derivative—the curvature of $f$ along direction $v$.

Second-Order Taylor Expansion:

Near point $x$, the function can be approximated as:

$$f(x + \Delta x) \approx f(x) + \nabla f(x)^T \Delta x + \frac{1}{2} \Delta x^T \nabla^2 f(x) \Delta x$$

The first three terms: constant, linear (gradient), and quadratic (Hessian). At a stationary point where $\nabla f(x) = 0$, the local behavior is entirely determined by the Hessian.

The Hessian provides additional information beyond what the gradient can tell us. At a local minimum, we can characterize the curvature.

Theorem (Second-Order Necessary Conditions):

If $x^*$ is a local minimum of twice-differentiable $f: \mathbb{R}^n \rightarrow \mathbb{R}$, then:

1. $\nabla f(x^*) = 0$ (first-order condition)
2. $\nabla^2 f(x^*) \succeq 0$ (Hessian is positive semidefinite)

Proof of (2):

Suppose $\nabla^2 f(x^*) \not\succeq 0$. Then there exists a direction $v$ with $|v| = 1$ such that:

$$v^T \nabla^2 f(x^*) v < 0$$

Using the Taylor expansion at $x^$ (where $\nabla f(x^) = 0$):

$$f(x^* + tv) = f(x^) + \frac{t^2}{2} v^T \nabla^2 f(x^) v + o(t^2)$$

For small $t$, the $t^2$ term dominates the $o(t^2)$ remainder. Since $v^T \nabla^2 f(x^*) v < 0$:

$$f(x^* + tv) < f(x^*)$$

This contradicts $x^*$ being a local minimum. $\square$

Understanding Positive Semidefiniteness:

A symmetric matrix $H$ is positive semidefinite ($H \succeq 0$) if any of these equivalent conditions hold:

1. $v^T H v \geq 0$ for all $v$ (non-negative curvature in all directions)
2. All eigenvalues of $H$ are $\geq 0$
3. $H = A^T A$ for some matrix $A$ (Cholesky-like factorization exists)
4. All principal minors are $\geq 0$ (Sylvester's criterion)

At a local minimum, condition (1) is the geometric requirement: we can't have negative curvature in any direction, or that direction would lead downhill.

Saddle Points:

At a saddle point, $\nabla f(x^) = 0$ but $\nabla^2 f(x^)$ has both positive and negative eigenvalues—positive curvature in some directions, negative in others. The point is a minimum in some directions and a maximum in others.

To guarantee a local minimum (not just rule out ascent directions), we need a stronger condition.

Theorem (Second-Order Sufficient Conditions):

If $f$ is twice continuously differentiable, $\nabla f(x^) = 0$, and $\nabla^2 f(x^) \succ 0$ (positive definite), then $x^*$ is a strict local minimum.

Proof:

Since $\nabla^2 f(x^*)$ is positive definite, let $\lambda_{\min} > 0$ be its smallest eigenvalue. For any unit vector $v$:

$$v^T \nabla^2 f(x^*) v \geq \lambda_{\min} > 0$$

By continuity of the Hessian, there exists $\epsilon > 0$ such that for $|x - x^*| < \epsilon$:

$$v^T \nabla^2 f(x) v \geq \frac{\lambda_{\min}}{2} > 0$$

For any $y$ with $|y - x^| < \epsilon$, consider the path from $x^$ to $y$:

$$f(y) = f(x^) + \int_0^1 \nabla f(x^ + t(y-x^))^T (y - x^) , dt$$

Using $\nabla f(x^*) = 0$ and expanding:

$$f(y) = f(x^) + \int_0^1 \int_0^s (y - x^)^T \nabla^2 f(x^* + \tau(y-x^)) (y - x^) , d\tau , ds$$

$$\geq f(x^) + \frac{\lambda_{\min}}{4} |y - x^|^2 > f(x^*)$$

So $x^*$ is a strict local minimum. $\square$

The Hessian provides a powerful way to verify global convexity, not just local behavior at critical points.

Theorem (Second-Order Characterization of Convexity):

Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be twice continuously differentiable. Then:

$$f \text{ is convex} \iff \nabla^2 f(x) \succeq 0 \text{ for all } x \in \text{dom}(f)$$

Proof ($\Rightarrow$):

If $f$ is convex, consider any point $x$ and direction $v$. The function $g(t) = f(x + tv)$ is a convex function of $t$. Its second derivative is:

$$g''(t) = v^T \nabla^2 f(x + tv) v$$

For convex $g$, we need $g''(t) \geq 0$, so $v^T \nabla^2 f(x) v \geq 0$ for all $v$. This means $\nabla^2 f(x) \succeq 0$.

Proof ($\Leftarrow$):

Assume $\nabla^2 f(x) \succeq 0$ everywhere. For any $x, y$, consider the path from $x$ to $y$:

$$f(y) = f(x) + \nabla f(x)^T(y-x) + \int_0^1 (1-t)(y-x)^T \nabla^2 f(x + t(y-x))(y-x) , dt$$

Since $(y-x)^T \nabla^2 f(\cdot)(y-x) \geq 0$ everywhere:

$$f(y) \geq f(x) + \nabla f(x)^T(y-x)$$

This is the first-order characterization of convexity. $\square$

Practical Convexity Verification:

To check if a function is convex:

1. Compute the Hessian $\nabla^2 f(x)$
2. Verify it's positive semidefinite for all $x$ in the domain
3. For PSD verification:
   • Check all eigenvalues $\geq 0$, or
   • Check all leading principal minors $\geq 0$, or
   • Attempt Cholesky decomposition

Example: Logistic Regression

For logistic loss $f(w) = \sum_{i} \log(1 + e^{-y_i x_i^T w})$:

The Hessian is:

$$\nabla^2 f(w) = \sum_{i} \sigma(y_i x_i^T w)(1 - \sigma(y_i x_i^T w)) x_i x_i^T = X^T D X$$

where $D$ is diagonal with $D_{ii} = \sigma_i(1 - \sigma_i) \geq 0$.

Since $X^T D X$ is a weighted sum of outer products with non-negative weights, it's PSD. Hence logistic loss is convex.

The eigenstructure of the Hessian provides deep geometric insight into the optimization landscape.

Eigenvalue Interpretation:

For symmetric Hessian $H = \nabla^2 f(x)$ with eigendecomposition $H = V \Lambda V^T$:

• Eigenvalues $\lambda_1, \ldots, \lambda_n$ are the curvatures along principal directions
• Eigenvectors $v_1, \ldots, v_n$ are the principal directions (mutually orthogonal)
• $\lambda_{\max}$ = maximum curvature = steepest direction
• $\lambda_{\min}$ = minimum curvature = flattest direction

Curvature in Direction $d$:

$$\kappa_d = \frac{d^T H d}{|d|^2}$$

This is bounded by eigenvalues: $\lambda_{\min} \leq \kappa_d \leq \lambda_{\max}$.

Condition Number:

The condition number of the Hessian (at a point, or the worst over the domain) is:

$$\kappa = \frac{\lambda_{\max}}{\lambda_{\min}}$$

This measures the "elongation" of the level sets:

• $\kappa = 1$: Isotropic (circular level sets), ideal for optimization
• $\kappa \gg 1$: Anisotropic (highly elongated ellipses), problematic for gradient descent

Why Condition Number Matters:

For gradient descent on a quadratic with Hessian $H$:

$$\text{Convergence rate} \propto \left(\frac{\kappa - 1}{\kappa + 1}\right)^2$$

For $\kappa = 100$ (moderately ill-conditioned): rate $\approx 0.96$, meaning 96% of the error remains each iteration. You need many iterations to converge.

For $\kappa = 10000$ (severely ill-conditioned): rate $\approx 0.9998$, meaning thousands of iterations for modest progress.

Preconditioning:

The solution to ill-conditioning is preconditioning: transforming the problem so the effective Hessian is better conditioned.

If we have an approximation $P \approx H$, we can solve the preconditioned system:

$$P^{-1} H x = P^{-1} b$$

The effective Hessian is $P^{-1} H$, which ideally has condition number close to 1.

Newton's method uses $P = H$ exactly, achieving perfect conditioning (but at computational cost). Quasi-Newton methods (BFGS, L-BFGS) build approximations to $H$ incrementally.

Strong convexity quantifies a lower bound on curvature, providing the strongest optimization guarantees.

Definition via Hessian:

Function $f$ is $m$-strongly convex if:

$$\nabla^2 f(x) \succeq m I \quad \forall x$$

Equivalently, all eigenvalues of the Hessian are at least $m$ everywhere.

Equivalent Definitions:

1. Quadratic lower bound: $$f(y) \geq f(x) + \nabla f(x)^T(y-x) + \frac{m}{2}|y - x|^2$$

2. Function definition: $$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y) - \frac{m}{2}\theta(1-\theta)|x-y|^2$$

3. $f(x) - \frac{m}{2}|x|^2$ is convex (subtracting a strongly convex function preserves convexity only if the original is at least that strongly convex).

Second-order conditions and Hessian analysis have direct applications throughout machine learning.

Newton's Method:

Newton's method uses the Hessian to take optimal steps for quadratic functions:

$$x_{k+1} = x_k - (\nabla^2 f(x_k))^{-1} \nabla f(x_k)$$

For quadratics, this converges in one step. For general smooth functions, it achieves quadratic convergence near the optimum:

$$|x_{k+1} - x^| = O(|x_k - x^|^2)$$

The error squares each iteration—convergence is extremely fast once close.

Trade-off: Newton's method requires computing and inverting the Hessian: $O(n^3)$ per iteration. For large-scale ML, this is prohibitive.

Quasi-Newton Methods (BFGS, L-BFGS):

These methods approximate the Hessian (or its inverse) using gradient observations:

• Build approximation $B_k \approx \nabla^2 f(x_k)$ incrementally
• Use $B_k$ to compute quasi-Newton direction
• Cost: $O(n^2)$ for BFGS, $O(nm)$ for L-BFGS (where $m \ll n$ is memory size)

L-BFGS is the workhorse for medium-scale ML optimization (logistic regression, CRFs, etc.).

Hessian-Free Optimization:

Instead of forming the full Hessian, compute Hessian-vector products $Hv$ efficiently using automatic differentiation:

$$Hv = \nabla_x (\nabla_x f \cdot v)$$

This costs about 2x a gradient computation. Combined with conjugate gradient, we can approximately solve $Hx = g$ without ever forming $H$.

Gauss-Newton Approximation:

For least-squares problems $f(w) = \frac{1}{2}|r(w)|^2$, the Hessian is:

$$\nabla^2 f = J^T J + \sum_i r_i \nabla^2 r_i$$

The Gauss-Newton approximation drops the second term:

$$\nabla^2 f \approx J^T J$$

This is always PSD (guaranteed descent direction) and cheaper to compute. It's the basis for Levenberg-Marquardt optimization.

Natural Gradient:

In probabilistic models, the Fisher information matrix plays the role of the Hessian in parameter space. Natural gradient descent uses Fisher (not Euclidean) geometry:

$$\theta_{k+1} = \theta_k - \eta F^{-1} \nabla \ell(\theta_k)$$

This gives parameter-independent convergence and is connected to second-order optimization.

The Hessian provides crucial curvature information that goes beyond what gradients can tell us. Let's consolidate:

What's Next:

With convex sets, functions, and optimality conditions established, we'll explore how convexity manifests across machine learning. The next page examines convexity in ML—which algorithms enjoy convex guarantees, which don't, and how to leverage convexity for reliable training.