Definition
Second-order optimization uses the Hessian , the matrix of second derivatives, as well as the gradient . The basic method is Newton's method: jump to the minimum of the local quadratic model, . Practical variants damp it, approximate , or only ever touch 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 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 :
- gradient: the slope, a vector of d numbers
- Hessian: , a symmetric matrix
- the quadratic model; Newton jumps to its stationary point
- the step. You solve ; you never form explicitly
Write with eigenvectors and eigenvalues . Then : the gradient component along each eigenvector is divided by that direction's curvature. Gradient descent multiplies every component by the same . On a quadratic bowl Newton lands on the minimum in one step, whatever the condition number . Gradient descent needs and then about steps per factor of progress along the flattest direction.
Newton is also affine invariant: rescaling or rotating the parameters () 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
- ; is pure Newton
- Local convergence
- quadratic: near a minimum with positive-definite
- Memory
- for ; parameters in float32 would need bytes (40 PB)
- Compute
- to factor ; 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
Why it converges so fast, and when it does not
Near a minimum where 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 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 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.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 | 4.78, 1020 | |
| 5 | (1.0000, 1.0000) | 0.40, 1002 | ||
| 6 | (1.0000, 1.0000) | 0.40, 1002 |
Worked example: one parameter of logistic regression
Fit a single logit to labels whose mean is 0.3: . Then and , and the minimum is . Newton's update is . (For full logistic regression this is the classical IRLS algorithm.)
Newton from w = 0 (verified numerically)
- 1: , , , step . Error .
- 2: , . Error .
- 3: error .
- 4: error .
- 5: error , machine precision. Each error is about the square of the previous one (): 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 has a negative eigenvalue , the component points uphill along , 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 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 instead of , so negative-curvature directions are followed downhill.
Damping and trust regions
- damping. gives Newton; gives the gradient step with learning rate
- trust-region radius; each corresponds to some (and )
Damping interpolates between Newton and gradient descent. Levenberg–Marquardt adapts each step by comparing the actual decrease with the decrease the model predicted: good agreement shrinks (more Newton-like), poor agreement grows it (more cautious). A fixed gives up quadratic convergence: in the figure, 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 parameters the Hessian has entries and solving with it costs . That is fine for and hopeless for a network with weights. The key escape is the Hessian-vector product (HVP): 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 (Pearlmutter, 1994).
- any direction, treated as a constant
- a scalar; differentiating it once more gives Hv (double backward)
With HVPs you can solve approximately by conjugate gradient, which needs only products with . That is Hessian-free optimization (Martens, 2010): a few CG iterations per update, damped, with the Gauss–Newton matrix in place of . HVPs also power the diagnostic tools: power iteration for the top Hessian eigenvalue (the "sharpness" used in Sharpness-aware minimization), Hutchinson's estimator , and the AdaHessian optimizer's diagonal estimate.
Curvature matrices that are always positive semi-definite
For a loss with network output , the Hessian splits into two parts. The Gauss–Newton part is , where and is the Hessian of the loss in output space. The other part involves the network's own second derivatives. Dropping the second part keeps positive semi-definite whenever is convex in (MSE, cross-entropy), so the step always goes downhill.
| method | curvature matrix | how it is made affordable | cost per step |
|---|---|---|---|
| Newton | exact solve (small models only) | ||
| Hessian-free | or via HVPs | a few damped conjugate-gradient iterations | HVPs, each ≈ 2 gradients |
| Gauss–Newton / Levenberg–Marquardt | (+ ) | exact for small least-squares problems | or CG |
| Natural gradient | Fisher | equals for cross-entropy with softmax; step is | needs an approximation |
| K-FAC | Fisher, per layer | (input-activation and output-gradient covariances), so inverting needs only the two small factors | per layer, amortized |
| Shampoo | per-layer preconditioner | left and right factors , of accumulated and for weight matrix gradient | matrix roots every few hundred steps |
| L-BFGS | low-rank estimate of | built from the last gradient differences |
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 can be read as a crude diagonal preconditioner in this family, which is part of why it copes with badly scaled layers.
1import torch2from torch.func import grad, hessian, jvp34# --- 1. Exact Newton on Rosenbrock (d = 2): fine when H is small ---5def f(t):6 x, y = t7 return (1 - x) ** 2 + 100 * (y - x ** 2) ** 289theta = 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 H14# ends at [1.0, 1.0] with f ≈ 3e-20 (the table above)1516# --- 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()}2021def loss_fn(p):22 return torch.nn.functional.mse_loss(torch.func.functional_call(model, p, (X,)), Y)2324def hvp(p, v): # H v at the cost of ~2 gradients25 return jvp(grad(loss_fn), (p,), (v,))[1]2627# --- 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())3536# 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)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
- − memory and 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 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 sends Newton toward saddles; use damping , Gauss–Newton/Fisher curvature, , or trust regions.
- ✓The exact Hessian costs memory and 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.