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.

13 min read1245 wordsadvanced0 viewsupdated 2026-10-11

Definition

Second-order optimization uses the Hessian H=∇2L(θ)H=\nabla^2L(\theta), the matrix of second derivatives, as well as the gradient g=∇L(θ)g=\nabla L(\theta). The basic method is Newton's method: jump to the minimum of the local quadratic model, θ←θ−H−1g\theta\leftarrow\theta-H^{-1}g. Practical variants damp it, approximate HH, or only ever touch HH 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 ∇L=0\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 ss:

L(θ+s)≈m(s)=L(θ)+g⊤s+12 s⊤Hs,∇sm=g+Hs=0  ⇒  sNewton=−H−1gL(\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=∇L(θ)g=\nabla L(\theta)
gradient: the slope, a vector of d numbers
H=∇2L(θ)H=\nabla^2 L(\theta)
Hessian: Hij=∂2L/∂θi∂θjH_{ij}=\partial^2L/\partial\theta_i\partial\theta_j, a symmetric d×dd\times d matrix
m(s)m(s)
the quadratic model; Newton jumps to its stationary point
ss
the step. You solve Hs=−gHs=-g; you never form H−1H^{-1} explicitly

Write H=QΛQ⊤H=Q\Lambda Q^\top with eigenvectors qiq_i and eigenvalues λi\lambda_i. Then −H−1g=−∑iqi⊤gλi qi-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 κ=λmax⁡/λmin⁡\kappa=\lambda_{\max}/\lambda_{\min}. Gradient descent needs η<2/λmax⁡\eta<2/\lambda_{\max} and then about κ\kappa steps per factor ee of progress along the flattest direction.

Newton is also affine invariant: rescaling or rotating the parameters (θ=Aϕ\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
θ←θ−(H+λI)−1g\theta\leftarrow\theta-(H+\lambda I)^{-1}g; λ=0\lambda=0 is pure Newton
Local convergence
quadratic: ∥θk+1−θ∗∥≤C∥θk−θ∗∥2\|\theta_{k+1}-\theta^*\|\le C\|\theta_k-\theta^*\|^2 near a minimum with positive-definite HH
Memory
O(d2)O(d^2) for HH; d=108d=10^8 parameters in float32 would need 4×10164\times10^{16} bytes (40 PB)
Compute
O(d3)O(d^3) to factor HH; 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
f = Rosenbrock (1−x)² + 100(y−x²)²×startf − f* (log) vs step1e-121e-81e-411e403060step× minimum · dots mark each Newton iterate
t = 0|
GD needs lr < 2/λmax (0.08 on the valley). Newton uses no learning rate; damped Newton solves (H + λI)s = −g. A negative eigenvalue (rose) means a saddle direction. Click a method to hide it.
fig.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 HH 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 (κ−1)/(κ+1)(\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 ff 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).

kθₖf(θₖ)‖θₖ − θ*‖eig(H)
0(−1.2000, 1.0000)24.22.2023.6, 1506
1(−1.1753, 1.3807)4.732.210.34, 1307
2(0.7631, −3.1750)14124.18149, 2022
3(0.7634, 0.5828)0.05600.4800.60, 668
4(1.0000, 0.9440)0.3135.6×10−25.6\times10^{-2}4.78, 1020
5(1.0000, 1.0000)1.9×10−111.9\times10^{-11}9.6×10−69.6\times10^{-6}0.40, 1002
6(1.0000, 1.0000)3.4×10−203.4\times10^{-20}1.9×10−111.9\times10^{-11}0.40, 1002
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.

Worked example: one parameter of logistic regression

Fit a single logit ww to labels whose mean is 0.3: L(w)=log⁡(1+ew)−0.3 wL(w)=\log(1+e^{w})-0.3\,w. Then L′(w)=σ(w)−0.3L'(w)=\sigma(w)-0.3 and L′′(w)=σ(w)(1−σ(w))L''(w)=\sigma(w)(1-\sigma(w)), and the minimum is w∗=ln⁡(0.3/0.7)=−0.847298w^*=\ln(0.3/0.7)=-0.847298. Newton's update is w←w−σ(w)−0.3σ(w)(1−σ(w))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. 1w0=0w_0=0: σ=0.5\sigma=0.5, L′=0.2L'=0.2, L′′=0.25L''=0.25, step −0.2/0.25=−0.8-0.2/0.25=-0.8. Error ∣w0−w∗∣=0.847|w_0-w^*|=0.847.
  2. 2w1=−0.8w_1=-0.8: L′=0.01003L'=0.01003, L′′=0.2139L''=0.2139. Error 4.7×10−24.7\times10^{-2}.
  3. 3w2=−0.846868w_2=-0.846868: error 4.3×10−44.3\times10^{-4}.
  4. 4w3=−0.84729782w_3=-0.84729782: error 3.7×10−83.7\times10^{-8}.
  5. 5w4w_4: error 1.1×10−161.1\times10^{-16}, machine precision. Each error is about 0.2×0.2\times the square of the previous one (0.2×(4.3×10−4)2=3.7×10−80.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 HH has a negative eigenvalue λi<0\lambda_i<0, the component −qi⊤gλiqi-\frac{q_i^\top g}{\lambda_i}q_i points uphill along qiq_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)(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 ∣λi∣|\lambda_i| instead of λi\lambda_i, so negative-curvature directions are followed downhill.

Damping and trust regions

s=−(H+λI)−1g=−∑iqi⊤gλi+λ qi⟺s=arg⁡min⁡∥s∥≤Δ  g⊤s+12s⊤Hss=-(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. λ→0\lambda\to0 gives Newton; λ→∞\lambda\to\infty gives the gradient step −g/λ-g/\lambda with learning rate 1/λ1/\lambda
Δ\Delta
trust-region radius; each Δ\Delta corresponds to some λ≥0\lambda\ge0 (and λ>−λmin⁡\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, λ=2\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 dd parameters the Hessian has d2d^2 entries and solving with it costs O(d3)O(d^3). That is fine for d=100d=100 and hopeless for a network with 10810^8 weights. The key escape is the Hessian-vector product (HVP): HvHv 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 HH (Pearlmutter, 1994).

Hv=∇θ(∇θL(θ)⊤v)=lim⁡r→0∇L(θ+rv)−∇L(θ)rHv=\nabla_\theta\big(\nabla_\theta L(\theta)^\top v\big)=\lim_{r\to0}\frac{\nabla L(\theta+rv)-\nabla L(\theta)}{r}
vv
any direction, treated as a constant
∇L⊤v\nabla L^\top v
a scalar; differentiating it once more gives Hv (double backward)

With HVPs you can solve Hs=−gHs=-g approximately by conjugate gradient, which needs only products with HH. That is Hessian-free optimization (Martens, 2010): a few CG iterations per update, damped, with the Gauss–Newton matrix in place of HH. HVPs also power the diagnostic tools: power iteration for the top Hessian eigenvalue (the "sharpness" used in Sharpness-aware minimization), Hutchinson's estimator E[v⊤Hv]=tr⁡H\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 ℓ(f(x;θ),y)\ell(f(x;\theta),y) with network output ff, the Hessian splits into two parts. The Gauss–Newton part is G=J⊤HℓJG=J^\top H_\ell J, where J=∂f/∂θJ=\partial f/\partial\theta and Hℓ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 GG positive semi-definite whenever ℓ\ell is convex in ff (MSE, cross-entropy), so the step always goes downhill.

methodcurvature matrixhow it is made affordablecost per step
NewtonHHexact solve (small models only)O(d3)O(d^3)
Hessian-freeGG or HH via HVPsa few damped conjugate-gradient iterationskk HVPs, each ≈ 2 gradients
Gauss–Newton / Levenberg–MarquardtJ⊤HℓJJ^\top H_\ell J (+ λI\lambda I)exact for small least-squares problemsO(d3)O(d^3) or CG
Natural gradientFisher F=E[∇log⁡p ∇log⁡p⊤]F=\mathbb E[\nabla\log p\,\nabla\log p^\top]FF equals GG for cross-entropy with softmax; step is −F−1g-F^{-1}gneeds an approximation
K-FACFisher, per layerFℓ≈A⊗SF_\ell\approx A\otimes S (input-activation and output-gradient covariances), so inverting needs only the two small factorsO(nin3+nout3)O(n_{in}^3+n_{out}^3) per layer, amortized
Shampooper-layer preconditionerleft and right factors L−1/4L^{-1/4}, R−1/4R^{-1/4} of accumulated GG⊤GG^\top and G⊤GG^\top G for weight matrix gradient GGmatrix roots every few hundred steps
L-BFGSlow-rank estimate of H−1H^{-1}built from the last mm gradient differencesO(md)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/v^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
1import torch
2from torch.func import grad, hessian, jvp
3
4# --- 1. Exact Newton on Rosenbrock (d = 2): fine when H is small ---
5def f(t):
6 x, y = t
7 return (1 - x) ** 2 + 100 * (y - x ** 2) ** 2
8
9theta = torch.tensor([-1.2, 1.0], dtype=torch.float64)
10for k in range(7):
11 g, H = grad(f)(theta), hessian(f)(theta)
12 print(k, theta.tolist(), f(theta).item())
13 theta = theta - torch.linalg.solve(H, g) # solve H s = g, never invert H
14# ends at [1.0, 1.0] with f ≈ 3e-20 (the table above)
15
16# --- 2. Hessian-vector product for a network: forward-over-reverse ---
17model = torch.nn.Sequential(torch.nn.Linear(10, 32), torch.nn.Tanh(), torch.nn.Linear(32, 1))
18X, Y = torch.randn(256, 10), torch.randn(256, 1)
19params = {k: v.detach() for k, v in model.named_parameters()}
20
21def loss_fn(p):
22 return torch.nn.functional.mse_loss(torch.func.functional_call(model, p, (X,)), Y)
23
24def hvp(p, v): # H v at the cost of ~2 gradients
25 return jvp(grad(loss_fn), (p,), (v,))[1]
26
27# --- 3. Top Hessian eigenvalue ("sharpness") by power iteration on HVPs ---
28v = {k: torch.randn_like(t) for k, t in params.items()}
29for _ in range(50):
30 Hv = hvp(params, v)
31 norm = torch.sqrt(sum((h ** 2).sum() for h in Hv.values()))
32 v = {k: h / norm for k, h in Hv.items()}
33lam_max = sum((h * v[k]).sum() for k, h in hvp(params, v).items())
34print("largest-magnitude eigenvalue of H:", lam_max.item())
35
36# The same HVP with classic autograd (double backward):
37# g = torch.autograd.grad(loss, params, create_graph=True)
38# 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

Use when

  • +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

Avoid when

  • −O(d2)O(d^2) memory and O(d3)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

Check yourself

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?

Check yourself

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

Remember

  • ✓Newton's step s=−H−1gs=-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 HH sends Newton toward saddles; use damping (H+λI)(H+\lambda I), Gauss–Newton/Fisher curvature, ∣H∣|H|, or trust regions.
  • ✓The exact Hessian costs O(d2)O(d^2) memory and O(d3)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.
← back to Deep Learning roadmap