# Second-order optimization

> Use curvature as well as slope: Newton's step −H⁻¹g rescales every direction by its own curvature and converges quadratically near a minimum. But the d×d Hessian costs O(d²) memory and O(d³) to solve, and saddles break it, so deep learning uses damped, approximate versions.

Source: https://www.mlfoundry.in/learn/second-order-optimization  
Section: Deep Learning › Optimization Algorithms  
Level: advanced · 13 min read · updated 2026-10-11

**Second-order optimization:** uses the **Hessian** $H=\nabla^2L(\theta)$, the matrix of second derivatives, as well as the gradient $g=\nabla L(\theta)$. The basic method is **Newton's method**: jump to the minimum of the local quadratic model, $\theta\leftarrow\theta-H^{-1}g$. Practical variants damp it, approximate $H$, or only ever touch $H$ through Hessian-vector products.

First-order methods (SGD, momentum, Adam) see only the slope. On an ill-conditioned surface, steep in one direction and flat in another, a single learning rate has to be small enough for the steepest direction, and the flat directions then crawl. The Hessian holds exactly the missing information: how quickly the slope changes in each direction. Dividing by it gives each direction a step matched to its own curvature, so a long narrow valley looks like a round bowl.

Newton's root-finding iteration goes back to Newton and Raphson in the 17th century. Applying it to $\nabla L=0$ gives Newton's method for optimization. Levenberg (1944) and Marquardt (1963) added **damping** to make it robust for least-squares fitting. In deep learning the line of work runs through Pearlmutter's exact **Hessian-vector product** (1994), Amari's **natural gradient** (1998), Martens' **Hessian-free optimization** (2010), Dauphin et al.'s analysis of **saddle points** (2014), and the Kronecker-factored preconditioners **K-FAC** (Martens and Grosse, 2015) and **Shampoo** (Gupta, Koren and Singer, 2018).

## Newton's step

Expand the loss to second order around the current point and minimize the model over the step $s$:

$$
L(\theta+s)\approx m(s)=L(\theta)+g^\top s+\tfrac12\,s^\top H s,\qquad \nabla_s m=g+Hs=0\;\Rightarrow\; s_{\text{Newton}}=-H^{-1}g
$$

- $g=\nabla L(\theta)$: gradient: the slope, a vector of d numbers
- $H=\nabla^2 L(\theta)$: Hessian: $H_{ij}=\partial^2L/\partial\theta_i\partial\theta_j$, a symmetric $d\times d$ matrix
- $m(s)$: the quadratic model; Newton jumps to its stationary point
- $s$: the step. You solve $Hs=-g$; you never form $H^{-1}$ explicitly

Write $H=Q\Lambda Q^\top$ with eigenvectors $q_i$ and eigenvalues $\lambda_i$. Then $-H^{-1}g=-\sum_i \frac{q_i^\top g}{\lambda_i}\,q_i$: the gradient component along each eigenvector is divided by that direction's curvature. Gradient descent multiplies every component by the same $\eta$. On a quadratic bowl Newton lands on the minimum in **one step**, whatever the condition number $\kappa=\lambda_{\max}/\lambda_{\min}$. Gradient descent needs $\eta<2/\lambda_{\max}$ and then about $\kappa$ steps per factor $e$ of progress along the flattest direction.

Newton is also **affine invariant**: rescaling or rotating the parameters ($\theta=A\phi$) gives exactly the same iterates. There is no learning rate to tune, because the curvature sets the step length. Gradient descent is invariant only to rotations.

**At a glance**

- **Update:** $\theta\leftarrow\theta-(H+\lambda I)^{-1}g$; $\lambda=0$ is pure Newton
- **Local convergence:** quadratic: $\|\theta_{k+1}-\theta^*\|\le C\|\theta_k-\theta^*\|^2$ near a minimum with positive-definite $H$
- **Memory:** $O(d^2)$ for $H$; $d=10^8$ parameters in float32 would need $4\times10^{16}$ bytes (40 PB)
- **Compute:** $O(d^3)$ to factor $H$; a Hessian-vector product costs about two gradients
- **Failure modes:** indefinite H (saddles), singular H, steps too long far from the minimum, noisy mini-batch curvature
- **Deep-learning forms:** Hessian-free (CG on Hv), Gauss–Newton, natural gradient, K-FAC, Shampoo, L-BFGS

> Figure: Gradient descent, pure Newton and damped Newton (H + λI)s = −g from the same start, with f − f* on a log scale. On the Rosenbrock function (start (−1.2, 1), Hessian eigenvalues 23.6 and 1506) GD at lr 0.001 is still at f = 3.93 after 60 steps; pure Newton first jumps to f = 1412 at step 2 and then reaches f < 1e-8 at step 5; damped Newton with λ = 2 takes 55 steps. On the κ = 25 valley Newton lands exactly on the minimum in one step. On the saddle surface the start has a negative eigenvalue (−0.99): pure Newton jumps straight to the saddle at (0, 0) and stays there with ‖g‖ = 0, while GD and damped Newton (λ = 2) reach a real minimum in 26 and 23 steps. Set λ = 1 there and H + λI is nearly singular, so the first step flies off to f − f* = 482.

## Why it converges so fast, and when it does not

Near a minimum $\theta^*$ where $H$ is positive definite and Lipschitz, the error after a Newton step is proportional to the **square** of the error before it: the number of correct digits roughly doubles every iteration. Gradient descent is only **linear**: the error shrinks by a constant factor, at best $(\kappa-1)/(\kappa+1)$ per step.

The guarantee is local. Far from the minimum the quadratic model can be a poor guide, and the full step can overshoot badly; on Rosenbrock the second Newton step raises $f$ from 4.7 to 1412 before the method recovers. Practical Newton methods therefore add a **line search** (shrink the step until the loss decreases enough) or a **trust region** (minimize the model only inside a ball where it is trusted).

Newton's method on Rosenbrock from (−1.2, 1), no damping, no line search (computed in Node with the figure's code). The last three rows show quadratic convergence.

| k | θₖ | f(θₖ) | ‖θₖ − θ*‖ | eig(H) |
| --- | --- | --- | --- | --- |
| 0 | (−1.2000, 1.0000) | 24.2 | 2.20 | 23.6, 1506 |
| 1 | (−1.1753, 1.3807) | 4.73 | 2.21 | 0.34, 1307 |
| 2 | (0.7631, −3.1750) | 1412 | 4.18 | 149, 2022 |
| 3 | (0.7634, 0.5828) | 0.0560 | 0.480 | 0.60, 668 |
| 4 | (1.0000, 0.9440) | 0.313 | $5.6\times10^{-2}$ | 4.78, 1020 |
| 5 | (1.0000, 1.0000) | $1.9\times10^{-11}$ | $9.6\times10^{-6}$ | 0.40, 1002 |
| 6 | (1.0000, 1.0000) | $3.4\times10^{-20}$ | $1.9\times10^{-11}$ | 0.40, 1002 |

## Worked example: one parameter of logistic regression

Fit a single logit $w$ to labels whose mean is 0.3: $L(w)=\log(1+e^{w})-0.3\,w$. Then $L'(w)=\sigma(w)-0.3$ and $L''(w)=\sigma(w)(1-\sigma(w))$, and the minimum is $w^*=\ln(0.3/0.7)=-0.847298$. Newton's update is $w\leftarrow w-\frac{\sigma(w)-0.3}{\sigma(w)(1-\sigma(w))}$. (For full logistic regression this is the classical IRLS algorithm.)

**Newton from w = 0 (verified numerically)**

1. $w_0=0$: $\sigma=0.5$, $L'=0.2$, $L''=0.25$, step $-0.2/0.25=-0.8$. Error $|w_0-w^*|=0.847$.
2. $w_1=-0.8$: $L'=0.01003$, $L''=0.2139$. Error $4.7\times10^{-2}$.
3. $w_2=-0.846868$: error $4.3\times10^{-4}$.
4. $w_3=-0.84729782$: error $3.7\times10^{-8}$.
5. $w_4$: error $1.1\times10^{-16}$, machine precision. Each error is about $0.2\times$ the square of the previous one ($0.2\times(4.3\times10^{-4})^2=3.7\times10^{-8}$): the digits double.

## Saddle points and indefinite Hessians

Newton's step is a step toward a **stationary point** of the quadratic model, not toward a minimum. If $H$ has a negative eigenvalue $\lambda_i<0$, the component $-\frac{q_i^\top g}{\lambda_i}q_i$ points **uphill** along $q_i$, so Newton is attracted to saddles and maxima just as much as to minima. That is what the figure's saddle surface shows: one step lands on $(0,0)$ and the gradient is exactly zero there.

This matters because in high dimensions saddles vastly outnumber local minima. Dauphin et al. (2014) argued that most critical points with high loss in neural networks are saddles, and that plateaus around them, not bad local minima, are what slow training. They proposed **saddle-free Newton**, which divides by $|\lambda_i|$ instead of $\lambda_i$, so negative-curvature directions are followed downhill.

> **Never trust a raw Newton step on a non-convex loss:** A neural-network Hessian is indefinite almost everywhere outside a minimum. Use damping $(H+\lambda I)$ with $\lambda>-\lambda_{\min}$, a positive semi-definite curvature approximation (Gauss–Newton, Fisher), $|H|$, or a trust region. Damping just at $-\lambda_{\min}$ is dangerous too: $H+\lambda I$ is then nearly singular and the step explodes, as the figure shows for $\lambda=1$ on the saddle surface.

## Damping and trust regions

$$
s=-(H+\lambda I)^{-1}g=-\sum_i\frac{q_i^\top g}{\lambda_i+\lambda}\,q_i\qquad\Longleftrightarrow\qquad s=\arg\min_{\|s\|\le\Delta}\;g^\top s+\tfrac12 s^\top Hs
$$

- $\lambda$: damping. $\lambda\to0$ gives Newton; $\lambda\to\infty$ gives the gradient step $-g/\lambda$ with learning rate $1/\lambda$
- $\Delta$: trust-region radius; each $\Delta$ corresponds to some $\lambda\ge0$ (and $\lambda>-\lambda_{\min}$)

Damping interpolates between Newton and gradient descent. Levenberg–Marquardt adapts $\lambda$ each step by comparing the actual decrease with the decrease the model predicted: good agreement shrinks $\lambda$ (more Newton-like), poor agreement grows it (more cautious). A fixed $\lambda$ gives up quadratic convergence: in the figure, $\lambda=2$ needs 26 steps on the valley, where Newton needs one, but it is safe on all three surfaces.

## Making it affordable: never form H

For $d$ parameters the Hessian has $d^2$ entries and solving with it costs $O(d^3)$. That is fine for $d=100$ and hopeless for a network with $10^8$ weights. The key escape is the **Hessian-vector product** (HVP): $Hv$ is the directional derivative of the gradient, so reverse-mode autodiff gets it exactly for about the cost of two gradient evaluations, without ever forming $H$ (Pearlmutter, 1994).

$$
Hv=\nabla_\theta\big(\nabla_\theta L(\theta)^\top v\big)=\lim_{r\to0}\frac{\nabla L(\theta+rv)-\nabla L(\theta)}{r}
$$

- $v$: any direction, treated as a constant
- $\nabla L^\top v$: a scalar; differentiating it once more gives Hv (double backward)

With HVPs you can solve $Hs=-g$ approximately by **conjugate gradient**, which needs only products with $H$. That is **Hessian-free optimization** (Martens, 2010): a few CG iterations per update, damped, with the Gauss–Newton matrix in place of $H$. HVPs also power the diagnostic tools: power iteration for the top Hessian eigenvalue (the "sharpness" used in **Sharpness-aware minimization**), Hutchinson's estimator $\mathbb E[v^\top Hv]=\operatorname{tr}H$, and the AdaHessian optimizer's diagonal estimate.

## Curvature matrices that are always positive semi-definite

For a loss $\ell(f(x;\theta),y)$ with network output $f$, the Hessian splits into two parts. The **Gauss–Newton** part is $G=J^\top H_\ell J$, where $J=\partial f/\partial\theta$ and $H_\ell$ is the Hessian of the loss in output space. The other part involves the network's own second derivatives. Dropping the second part keeps $G$ positive semi-definite whenever $\ell$ is convex in $f$ (MSE, cross-entropy), so the step always goes downhill.

| method | curvature matrix | how it is made affordable | cost per step |
| --- | --- | --- | --- |
| Newton | $H$ | exact solve (small models only) | $O(d^3)$ |
| Hessian-free | $G$ or $H$ via HVPs | a few damped conjugate-gradient iterations | $k$ HVPs, each ≈ 2 gradients |
| Gauss–Newton / Levenberg–Marquardt | $J^\top H_\ell J$ (+ $\lambda I$) | exact for small least-squares problems | $O(d^3)$ or CG |
| Natural gradient | Fisher $F=\mathbb E[\nabla\log p\,\nabla\log p^\top]$ | $F$ equals $G$ for cross-entropy with softmax; step is $-F^{-1}g$ | needs an approximation |
| K-FAC | Fisher, per layer | $F_\ell\approx A\otimes S$ (input-activation and output-gradient covariances), so inverting needs only the two small factors | $O(n_{in}^3+n_{out}^3)$ per layer, amortized |
| Shampoo | per-layer preconditioner | left and right factors $L^{-1/4}$, $R^{-1/4}$ of accumulated $GG^\top$ and $G^\top G$ for weight matrix gradient $G$ | matrix roots every few hundred steps |
| L-BFGS | low-rank estimate of $H^{-1}$ | built from the last $m$ gradient differences | $O(md)$ |

The natural gradient makes the step invariant to how the model is parameterized, because it measures distance by the change in the predicted distribution (KL divergence) rather than in parameter space. Adam's $1/\sqrt{\hat v}$ can be read as a crude diagonal preconditioner in this family, which is part of why it copes with badly scaled layers.

```python
import torch
from torch.func import grad, hessian, jvp

# --- 1. Exact Newton on Rosenbrock (d = 2): fine when H is small ---
def f(t):
    x, y = t
    return (1 - x) ** 2 + 100 * (y - x ** 2) ** 2

theta = torch.tensor([-1.2, 1.0], dtype=torch.float64)
for k in range(7):
    g, H = grad(f)(theta), hessian(f)(theta)
    print(k, theta.tolist(), f(theta).item())
    theta = theta - torch.linalg.solve(H, g)          # solve H s = g, never invert H
# ends at [1.0, 1.0] with f ≈ 3e-20 (the table above)

# --- 2. Hessian-vector product for a network: forward-over-reverse ---
model = torch.nn.Sequential(torch.nn.Linear(10, 32), torch.nn.Tanh(), torch.nn.Linear(32, 1))
X, Y = torch.randn(256, 10), torch.randn(256, 1)
params = {k: v.detach() for k, v in model.named_parameters()}

def loss_fn(p):
    return torch.nn.functional.mse_loss(torch.func.functional_call(model, p, (X,)), Y)

def hvp(p, v):                                        # H v at the cost of ~2 gradients
    return jvp(grad(loss_fn), (p,), (v,))[1]

# --- 3. Top Hessian eigenvalue ("sharpness") by power iteration on HVPs ---
v = {k: torch.randn_like(t) for k, t in params.items()}
for _ in range(50):
    Hv = hvp(params, v)
    norm = torch.sqrt(sum((h ** 2).sum() for h in Hv.values()))
    v = {k: h / norm for k, h in Hv.items()}
lam_max = sum((h * v[k]).sum() for k, h in hvp(params, v).items())
print("largest-magnitude eigenvalue of H:", lam_max.item())

# The same HVP with classic autograd (double backward):
# g = torch.autograd.grad(loss, params, create_graph=True)
# Hv = torch.autograd.grad(g, params, grad_outputs=v)
```

Exact Newton on a small problem, then Hessian-vector products and the top eigenvalue for a real network

> **Curvature is why learning rates have limits:** Gradient descent on a quadratic is stable only for $\eta<2/\lambda_{\max}$: the steepest direction alone sets the ceiling. Newton removes the ceiling by dividing by the curvature. Many first-order tricks are partial answers to the same problem: momentum, Adam's per-parameter scaling, batch and layer normalization (which improve conditioning), and warmup (which waits while $\lambda_{\max}$ falls early in training).

> **Why SGD and Adam still win most of the time:** Deep-learning gradients are mini-batch estimates, and curvature estimated from a mini-batch is noisier still. Second-order steps assume an accurate local model, so they need larger batches and careful damping. Each step also costs several gradient evaluations. For most networks a well-tuned first-order method gets further per unit of compute. Second-order ideas pay off where curvature is extreme and data is plentiful: K-FAC for large-batch training, Shampoo (a distributed version won the external-tuning track of the 2024 AlgoPerf benchmark), and exact or quasi-Newton methods for small, deterministic problems.

**Strengths**

- Quadratic convergence near a minimum: digits double per step
- No learning rate: curvature sets the step length in every direction
- Invariant to affine reparameterization; immune to ill-conditioning on quadratics
- Hessian-vector products give exact curvature information for about two gradients' cost

**Limitations**

- $O(d^2)$ memory and $O(d^3)$ compute for the exact Hessian
- Attracted to saddle points and maxima when H is indefinite
- Full steps can overshoot far from the minimum; needs damping, line search or a trust region
- Mini-batch curvature is noisy; each step costs several gradient evaluations

**Question:** At the current point the Hessian has eigenvalues 4 and −2, and the gradient has components 8 and 2 along the two eigenvectors. What does the pure Newton step do along the second eigenvector?

- A. Moves +1 along it, uphill in that direction
- B. Moves −1 along it, downhill
- C. Nothing: Newton ignores negative curvature
- D. Moves −4 along it

**Answer:** A. Moves +1 along it, uphill in that direction — The Newton component is $-g_2/\lambda_2=-2/(-2)=+1$, in the direction of the gradient component, which is uphill. Along the first eigenvector it moves $-8/4=-2$, downhill. With negative curvature the quadratic model has a maximum along $q_2$, and Newton heads for it: this is how Newton gets attracted to saddles.

**Question:** Why can deep-learning frameworks use exact Hessian information for a 100-million-parameter model at all?

- A. They store the Hessian in float16
- B. Hessian-vector products Hv cost about two gradient evaluations and never form H
- C. The Hessian of a neural network is diagonal
- D. They only compute the Hessian of the last layer

**Answer:** B. Hessian-vector products Hv cost about two gradient evaluations and never form H — $Hv=\nabla(\nabla L^\top v)$ is one more pass of automatic differentiation (Pearlmutter's trick). Conjugate gradient, power iteration and Hutchinson's trace estimator all need only products with $H$, so the $10^{16}$-entry matrix is never built.

**Key points**

- Newton's step $s=-H^{-1}g$ minimizes the local quadratic model; it divides each eigen-direction's gradient by its curvature.
- Exact on quadratics in one step, quadratic convergence near a minimum, no learning rate, affine invariant.
- Indefinite $H$ sends Newton toward saddles; use damping $(H+\lambda I)$, Gauss–Newton/Fisher curvature, $|H|$, or trust regions.
- The exact Hessian costs $O(d^2)$ memory and $O(d^3)$ to solve; Hessian-vector products cost about two gradients.
- Deep-learning forms: Hessian-free (CG on HVPs), natural gradient, K-FAC, Shampoo, and quasi-Newton L-BFGS.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
