Advanced 45 min read newtonhessianl-bfgscurvaturequasi-newton

Second-Order Methods

Newton's method, why the Hessian is impractical, and when L-BFGS is used.

Gradient descent uses only the first derivative of the loss: which direction is downhill from here. It does not know how steep that downhill is or how quickly it levels off — it cannot see curvature.

This is why the learning rate must be tuned so carefully: it is a proxy for curvature information the optimizer does not have. Newton's method has that information. The Hessian H is the matrix of second derivatives — it encodes the curvature in every parameter direction simultaneously. Newton's step θ ← θ − H^{-1}·∇L is the exact minimizer of the local quadratic approximation of the loss. For a perfectly quadratic loss, one Newton step lands at the minimum. For smooth strongly convex functions, convergence is quadratic — the error roughly doubles the number of correct digits at each step.

The fundamental problem is scale: the Hessian of a network with n parameters is n×n. For n=10^6, the Hessian has 10^12 entries requiring 4 TB of memory, and inverting it requires 10^18 floating-point operations. At the compute capacity of a modern GPU (about 10^14 FLOP/s), one Newton step takes on the order of three hours — before any training has occurred. Quasi-Newton methods approximate the inverse Hessian from gradient information across recent steps rather than computing it exactly. L-BFGS builds a low-rank approximation using the last m gradient pairs at O(mn) cost. It is the right tool when n is small enough (below roughly 10^5 parameters) and full-batch gradient evaluation is affordable — scientific computing, physics simulations, hyperparameter optimization inner loops. At the scale of deep learning, it is not used in production because the cost of even an approximate Hessian exceeds the cost of many gradient steps.

Raw Newton overshoots: line search and trust regions

The clean "one step to the minimum" story only holds for a *truly quadratic* loss. Real losses aren't quadratic, so the full Newton step H⁻¹∇L can badly overshoot — the local quadratic model is only accurate near the current point. So practical second-order methods never take the raw step. They add a line search (compute the Newton *direction*, then search along it for a step length that actually decreases the loss) or a trust region (only trust the quadratic model within a bounded radius, and cap the step to that region, shrinking it when the model proves inaccurate). Newton without damping or line search is a good way to diverge.

The Hessian can point the wrong way

Newton's method assumes the Hessian is positive definite (the loss curves *up* in every direction, a bowl). In the non-convex landscapes of deep nets that's often false: at a saddle point the Hessian is indefinite (curves up some ways, down others). Then H⁻¹∇L can point *toward* the saddle or even a local *maximum* rather than a minimum — the raw Newton step actively moves the wrong way. This is why non-convex second-order methods must modify the Hessian (add damping λI to make it positive definite, or flip negative curvature) before inverting. Raw Newton is a convex-optimisation tool.

What ML actually uses: Gauss-Newton and the Fisher

Because the true Hessian is expensive *and* can be indefinite, ML rarely uses it directly. Two better-behaved substitutes dominate. The Gauss-Newton matrix approximates the Hessian using only first-derivative (Jacobian) information and is guaranteed positive semi-definite — no wrong-way steps. The closely-related Fisher information matrix underlies natural gradient methods (and K-FAC), which precondition the gradient by the Fisher instead of the Hessian. Both give curvature-aware steps without the true Hessian's indefiniteness — which is why "second-order in ML" almost always means Gauss-Newton / Fisher / natural-gradient, not literal Newton.

Where L-BFGS shines — and where it doesn't

Sharpen the use-map. L-BFGS is excellent for small, deterministic, full-batch objectives: classical ML models (logistic regression, CRFs), scientific/physics optimisation, style-transfer-style problems, and small full-batch fine-tuning where you can afford exact gradients. It is a poor fit for noisy, large-scale mini-batch deep learning, because batch noise corrupts the gradient-difference curvature estimates (they can go indefinite and point uphill), and full-batch gradients over millions of examples cost as much as many SGD steps. Rule of thumb: L-BFGS when the gradient is exact and parameters are modest; SGD/Adam when the gradient is a noisy mini-batch estimate.

Adam is not literally diagonal Newton

A common over-statement: "Adam is a diagonal approximation to the Hessian." Be precise — Adam divides by the running second moment of the *gradients* (E[g²]), which is *not* the diagonal of the Hessian (that would be second *derivatives*). It's better described as curvature-*like* adaptive preconditioning: dividing by the gradient's recent magnitude gives each parameter its own effective step, which *behaves* somewhat like inverse-curvature scaling but isn't derived from the Hessian. Useful intuition, imprecise identity — worth stating correctly in an interview.

The optimizer decision tree (and a precision note)

Choosing among them comes down to a few axes: dataset/parameter size, gradient noise (batch vs full-batch), and objective stability. AdamW — the default for large, noisy, mini-batch deep learning (transformers, most nets). SGD+momentum — competitive/better in well-tuned vision/CNN settings. L-BFGS — small-to-medium, full-batch, deterministic objectives and classical ML. Newton / IRLS — very small, convex, well-conditioned problems (IRLS is Newton's method for logistic-regression-style GLMs). K-FAC / natural gradient — when the per-step second-order gain outweighs 2–5× overhead, mostly research. (One precision footnote: the "4 TB Hessian" figure assumes float32; in float64 it's 8 TB — the exact number depends on precision, but the point that it's hopeless stands either way.)

Key points

Gradient descent's learning rate problem exists because the optimizer has no curvature information. The optimal step size in any direction is 1/(curvature in that direction). Without the Hessian, you must guess this — which is why the learning rate is the most sensitive hyperparameter. Newton's method eliminates this problem by computing the step directly from curvature: θ ← θ − H^{-1}∇L.
Newton's step solves the local quadratic approximation exactly. If the loss were truly quadratic (a bowl), one Newton step would land at the minimum regardless of starting point. For non-quadratic losses, Newton's method requires iteration but converges quadratically: after reaching the basin of the minimum, each step roughly doubles the number of correct digits. Gradient descent converges linearly — it takes a fixed fraction off the remaining error at each step, never accelerating.
The Hessian is impractical at modern network sizes. For n parameters, H has n² entries. At n=10^6: 10^12 float32 values = 4 TB of memory. Inverting H costs O(n^3) = 10^18 operations. A GPU computing at 10^14 FLOP/s would need 10,000 seconds per training step — compared to milliseconds for a gradient step. The theoretical optimality of Newton's method is irrelevant when the method is computationally infeasible.
L-BFGS circumvents full Hessian storage by approximating H^{-1} from the last m gradient difference pairs. At each step it records δ_t = θ_t − θ_{t-1} and γ_t = ∇L_t − ∇L_{t-1}. The two-loop recursion computes H^{-1}·∇L using only these pairs, at O(mn) cost per step. With m=10–30 at the n=10^6 scale established above, this is roughly a 10^10–10^11x reduction in cost over exact Newton (the per-step cost drops from O(n^3) to O(mn), a factor of n²/m). The catch: L-BFGS requires full-batch gradients to build a reliable curvature model. Mini-batch gradient differences are corrupted by batch noise, making the approximation unreliable.
L-BFGS requiring full-batch gradients is the barrier to large-scale deep learning use. At N=1M training examples, one L-BFGS step requires evaluating the gradient over all 1M examples — as expensive as many SGD steps. Additionally, the curvature model is only valid for a region around the current parameters; for large networks navigating a complex loss landscape, the approximation degrades quickly. L-BFGS is used in deep learning only for small fine-tuning tasks, some meta-learning inner loops, and classical ML models with few parameters.
K-FAC approximates the Fisher information matrix using the Kronecker product structure of neural network layers. Each layer's curvature block is approximated as a Kronecker product of two much smaller matrices, reducing memory from O(n²) to O(n). K-FAC has achieved faster convergence per step than SGD on ResNets, but each step costs 2–5x more in wall-clock time — and the benefit does not reliably outweigh the overhead in production training pipelines.
Deep learning uses first-order methods not because they are theoretically superior but because they are the only methods that scale. Second-order information would improve every training step. The problem is that gathering and using that information costs more than taking many first-order steps in its place. Adam is a cheap *curvature-like* adaptive preconditioner — dividing by the running second moment of the *gradients* (not the Hessian's diagonal, which would be second derivatives) — and that is the best practical approximation available at million-parameter scale.
Raw Newton is unsafe on real losses — it needs damping, and ML prefers PSD substitutes. The full step H⁻¹∇L overshoots on non-quadratic losses (fix with line search or a trust region) and, at a saddle point where the Hessian is indefinite, can point toward a saddle or maximum (fix by adding λI to make it positive definite). This is why ML rarely uses the true Hessian: Gauss-Newton and the Fisher information matrix are positive-semi-definite by construction, so natural-gradient / K-FAC methods get curvature-aware steps without the wrong-way risk.
Pick the optimizer by scale, noise, and stability. AdamW for large noisy mini-batch deep learning; SGD+momentum for well-tuned vision/CNNs; L-BFGS for small-to-medium full-batch deterministic objectives and classical ML (it fails on noisy mini-batches because gradient-difference curvature goes indefinite); Newton/IRLS for tiny convex problems (IRLS is Newton for GLMs); K-FAC/natural gradient only when the per-step gain beats the 2–5× overhead. The "4 TB Hessian" figure is float32 — float64 doubles it, but either way it's infeasible.

Takeaway

Second-order methods would give optimal steps if you could afford them. Newton's method converges in a handful of steps for well-conditioned problems. The Hessian for a million-parameter network requires 4 TB of memory and 10^18 operations to invert — which is why we use gradient descent. Every adaptive optimizer from AdaGrad to Adam is a practical approximation to diagonal Newton steps, not a theoretical preference for first-order methods.

Recap

Plain GD sees no curvature at all: it only knows the slope, so the learning rate is a single hand-tuned proxy for the per-direction curvature it can't measure — the root of the ravine/condition-number problem.
Newton's step uses the full curvature: θ ← θ − H⁻¹∇L exactly minimizes the local quadratic and gives *quadratic* convergence (the number of correct digits doubles each step) on well-conditioned problems — a handful of steps to converge.
But the Hessian is infeasible at scale: for n=10⁶ parameters it has 10¹² entries (~4 TB in float32) and costs O(n³) ≈ 10¹⁸ operations to invert — which is exactly why we settle for gradient descent and cheap curvature approximations.
L-BFGS approximates H⁻¹ from just the last m gradient/step pairs at O(mn) cost — excellent for small-to-medium, *full-batch*, deterministic objectives (classical ML), but it fails on noisy mini-batches because the gradient-difference curvature estimate goes indefinite.
Raw Newton is actually unsafe on real losses: it overshoots non-quadratic bowls (needs a line search or trust region) and steps the *wrong way* at indefinite saddle points where some curvatures are negative (needs damping) — you can't just apply the formula.
ML uses PSD substitutes instead: Gauss-Newton and the Fisher matrix (natural gradient, K-FAC) are always positive semi-definite, so they're curvature-aware without ever taking a wrong-way step — use them only when the per-step gain beats the 2–5× overhead.
Adam is *not* diagonal Newton: it divides by the gradients' second moment E[g²], not the Hessian's diagonal — curvature-*like* preconditioning that helps in practice, but don't claim it as the true second-order identity in an interview.

Check your understanding

Q1. A 3-parameter loss function has Hessian H = [[4, 0, 0], [0, 1, 0], [0, 0, 100]] and gradient g = [2, 1, 10]. Compare the gradient descent step (α=0.01) to the Newton step. What does this reveal about condition number?

`A) Gradient descent step: δ = −α·g = [−0.02, −0.01, −0.1]. Newton step: δ = −H^{-1}·g = [−0.5, −1.0, −0.1]. Curvature 4 → Newton takes 0.5 vs GD's 0.02; curvature 1 → Newton 1.0 vs GD's 0.01; curvature 100 → both take 0.1. Condition number = 100/1 = 100: one learning rate can't be right for both curvature 1 and curvature 100 at once — Newton adapts the step to each direction's curvature automatically, which no single global learning-rate schedule can substitute for.`
`B) Gradient descent step: δ = [−0.02, −0.01, −0.1]. Newton step: δ = [−0.5, −0.5, −0.5] — Newton's method takes equal steps in all directions because it normalizes by the trace of the Hessian divided by 3, computing an isotropic approximate curvature. The condition number measures how far this approximation is from the true per-direction curvature, and a condition number of 100 means Newton's approximation is 100x off from gradient descent in the worst-case direction.`
`C) Gradient descent and Newton's method produce identical steps when the Hessian is diagonal. For diagonal H, H^{-1}·g = [g_1/H_11, g_2/H_22, g_3/H_33] = [0.5, 1.0, 0.1], which matches gradient descent step [0.02, 0.01, 0.1] scaled by 1/α = 25. The condition number of 100 indicates that Newton's method takes exactly 100x larger steps than gradient descent in every coordinate, which is why Newton converges faster but requires a trust-region radius of 1/100 to remain stable.`
`D) Newton's step is always identical to the gradient descent step when α = 1/max_eigenvalue. For H with max eigenvalue 100, α=0.01 makes gradient descent take the same step as Newton only for the third parameter (curvature 100). The condition number 100/1 = 100 quantifies how many learning rates would be needed to match Newton in all directions simultaneously — with condition number 100, you'd need 100 different learning rates, one per decade of curvature, to mimic Newton with gradient descent.`

Q2. Why does L-BFGS require full-batch gradients rather than mini-batch gradients? What happens when you try to use mini-batch gradients with L-BFGS?

`A) L-BFGS builds its Hessian approximation from gradient differences: γ_t = ∇L(θ_t) − ∇L(θ_{t-1}). With full-batch gradients this accurately reflects how the true gradient changes as parameters move. With mini-batch gradients, γ_t = ∇L_{B_t}(θ_t) − ∇L_{B_{t-1}}(θ_{t-1}) confounds the parameter-update change with the change in *which batch* was sampled — batch noise corrupts the curvature estimate, which can go indefinite and point the quasi-Newton direction uphill, degenerating to worse than SGD.`
`B) L-BFGS requires full-batch gradients because its line search procedure is only valid when the loss function is deterministic. With mini-batch gradients, the same parameter vector θ gives different gradient values at each step, violating the Armijo sufficient decrease condition that L-BFGS's line search relies on. The line search either never terminates or accepts steps that increase the true loss. Full-batch gradients make the loss deterministic at each θ, allowing the line search to function correctly.`
`C) L-BFGS requires full-batch gradients only for convergence guarantees, not for correctness. With mini-batch gradients, L-BFGS converges to a neighborhood of the minimum rather than the minimum itself, with the neighborhood size proportional to the gradient variance. Practitioners often use L-BFGS with large mini-batches (B=10,000+) to get a good trade-off between speed and convergence quality. The degradation to worse-than-SGD only occurs at very small batch sizes.`
`D) L-BFGS cannot use mini-batch gradients because its memory buffer stores gradient vectors rather than gradient differences. With B=32 mini-batches, each stored gradient vector reflects a random subset of 32 examples, and the m=20 stored vectors represent 20 different random subsets. The Hessian approximation built from these vectors reflects the curvature of 20 different loss functions simultaneously, not the curvature of the true loss function, producing an incoherent direction that diverges.`

Q3. K-FAC achieves faster convergence in steps than SGD for ResNet training. Yet practitioners still use SGD for production ImageNet training. Why?

`A) Practitioners use SGD because K-FAC's faster per-step convergence only applies to the first 50% of training. In later training, SGD's implicit regularization from gradient noise helps it find flatter minima, while K-FAC's precise updates converge to the nearest local minimum. The total training time for both methods is similar, and SGD produces better test accuracy in the second half of training, making it the preferred choice.`
`B) K-FAC is not actually faster in practice — the faster convergence is observed in controlled experiments with specific small datasets where the Fisher matrix approximation is accurate. On ImageNet's diverse and noisy gradient signal, K-FAC's Fisher estimate drifts rapidly and converges at the same rate as SGD. The step-count advantage disappears at N=1.2M examples because the Fisher information estimate is never stable enough to be useful.`
`C) The reason practitioners use SGD is regulatory: ImageNet competition rules and academic benchmark standards require SGD with specific hyperparameters for comparison purposes. K-FAC produces better results technically but cannot be used in standard benchmarks because it is not a fair comparison with published SGD baselines — reviewers reject any optimizer besides SGD with momentum 0.9. This is an institutional constraint, not a technical one.`
`D) K-FAC requires computing and inverting per-layer Fisher matrices each step — even with the Kronecker trick this adds 2-5x cost per step vs SGD, so 2x fewer steps at 4x cost per step is net slower wall-clock. It also brings extra sensitive hyperparameters (damping, factor/inversion update frequency) practitioners lack intuition for, and SGD's gradient noise tends to find flatter, better-generalizing minima that K-FAC's more precise updates can miss even at matched training loss.`

Q4. You implement raw Newton's method (θ ← θ − H⁻¹∇L) on a non-convex neural-net loss and it sometimes moves the loss *up* or diverges. Which two of the following correctly explain why, and how each is addressed?

`A) Non-quadratic losses make the full Newton step overshoot, since the local quadratic model is only accurate near the current point — fixed with a line search along the Newton direction, or a trust region that caps the step size.`
`B) Newton's method is simply buggy on GPUs due to floating-point rounding error in the matrix inverse; switching entirely to float64 precision resolves the divergence and guarantees monotonic descent on any loss surface.`
`C) At a saddle point the Hessian is indefinite (not positive definite), so H⁻¹∇L can point toward the saddle or even a local maximum — fixed by damping the Hessian (adding λI) or substituting the positive-semi-definite Gauss-Newton or Fisher matrix.`
`D) The Hessian is simply too large to invert exactly at neural-net scale, so the approximate inverse points in a random direction; using the mathematically exact inverse removes this problem and Newton then always descends monotonically.`

Q5. An interviewer says "Adam is basically a diagonal approximation to Newton's method." How would you make that statement more precise?

`A) It's exactly right — Adam computes the diagonal of the Hessian (the actual second partial derivatives ∂²L/∂θᵢ²) via a running average and divides the gradient by that diagonal, which is literally diagonal Newton with no approximation.`
`B) It's a useful intuition but imprecise. Adam divides by the running second moment of the *gradients* (E[g²]) — not the Hessian's diagonal, which needs actual second derivatives. Better called curvature-*like* preconditioning, not literal second-order information.`
`C) It's completely wrong — Adam has nothing to do with curvature; it only implements momentum plus a bias-correction term, and any resemblance to second-order preconditioning is purely coincidental, not a designed property of the rule.`
`D) It's precise exactly as stated, because the Fisher information matrix equals the Hessian for any twice-differentiable loss, and Adam's running second-moment estimate E[g²] equals the Fisher diagonal to first order near convergence.`

Try it interactively

ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.

Open ML Systems Lab →