AIML Rounds RoadmapMocksJobs

Newton's Method and Second-Order Optimisation

What is Newton's method, and why isn't it used to train deep networks?

The situation

A colleague says Newton's method converges in very few steps and doesn't need a learning rate, so why not train your deep model with it? Meanwhile, your logistic regression solver uses something called L-BFGS. The interviewer asks:

What is Newton's method, and why isn't it used to train deep networks?

Why it matters

This is a common interview question, and the answer explains why deep learning uses Adam, not a seemingly better method. These ideas are still used directly in logistic regression and gradient boosting. See Taylor series first.

The idea

Think of hiking down a valley. Gradient descent only feels the slope underfoot, so it takes cautious steps. Newton also has a map of how the land curves, and jumps straight to the bottom of the local bowl. It's a great jump, but drawing that map for a million-dimensional land is impossibly costly.

Gradient descentSlope onlyCheap stepsNewtonExact curvaturen² memoryL-BFGSCurvature fromrecent stepsIn between
Newton wins per step, and loses on what each step costs.

Play

Try to break it. Raise the condition number, then raise the weights.

Compare the two methods

Fast steps against huge costs
gradient descent steps
–
Newton steps
–
Hessian size
–
gradient size
–

On a pure quadratic, using gradient descent's best fixed learning rate, to reduce the error a million times. Real losses aren't quadratic, so Newton needs several steps. Assumes 4 bytes per number.

Raise the condition number: gradient descent's steps grow in proportion, and Newton's stay at one. Now raise the weights: the memory needed for the Hessian grows a hundred times for every tenfold increase. Newton wins per step, and loses on what each step costs.

Now say why: why does the Hessian's memory grow so much faster than the gradient's?

Maths

In one breath

Gradient descent only uses slope, so it needs a learning rate and struggles when curvature differs by direction. Newton's method jumps to the minimum of the local quadratic: w − H⁻¹g. It's scale-free and converges very fast near a solution. But with n weights, the Hessian has n² entries and n³ solving cost, and it can head towards saddle points. So deep learning sticks to first-order methods, while L-BFGS and Newton-style boosting work well on smaller or convex problems.

Using curvature

Where the step comes from

Take the second-order Taylor approximation, and jump straight to its minimum by setting its gradient to zero: g + HΔ = 0, so Δ = −H⁻¹g. It scales each direction by its curvature, taking long steps where the loss is flat and short ones where it's sharp.

How it compares

Gradient descentNewtonL-BFGS
UsesSlopeSlope and exact HessianSlope and recent history
Learning rateNeeds tuningNatural step of 1Usually a line search
Memorynn²About 2mn, for m past steps
Cost per stepn, per examplen³ to solveAbout mn
Near the solutionSteadyVery fast, doubling correct digitsFast

Why deep learning doesn't use it

  • Size: a million weights gives a trillion Hessian entries.
  • Saddle points: Newton looks for any flat point, so with mixed-sign curvature, it can move towards a saddle.
  • Noise: mini-batches give noisy curvature estimates, and approximate curvature methods are sensitive to this.

Where these ideas are used

  • Logistic regression: Newton's method, as IRLS, and L-BFGS are common solvers, as the problem is convex and small enough.
  • Gradient boosting: XGBoost-style trees use first and second derivatives of the loss per example. See gradient boosting.
  • Adam: it divides by a running estimate of squared gradients, which acts as a rough per-weight scale. It isn't true curvature, but it has a similar spirit.

The maths

    Example: f(x) = x² − 4x. At x = 10, g = 16 and H = 2, so the step is 8, and you land on the minimum at x = 2 in one go.

    In practice

    In practice

    • Small, convex problems: L-BFGS is often a great default, because it needs no learning rate.
    • Don't store the Hessian: Hessian-free methods use conjugate gradient with Hessian-vector products, so they only need matrix-vector operations.
    • Natural gradient: similar in spirit, using the Fisher matrix. K-FAC approximates it for neural networks.
    • Damping and line search: plain Newton can overshoot far from the solution. Both make it more robust.
    • Full batch: L-BFGS expects fairly accurate gradients, so it suits full or large batches rather than noisy ones.

    The answer that sounds right

    "Newton's is better because it converges in fewer steps"

    It sounds right, as fewer steps looks like less work. But steps aren't the cost: each one needs the full Hessian. With a million weights, that's four terabytes, plus an n³ solve, while a gradient step costs almost nothing. What matters is total time to a good result, and on large models, first-order methods win.

    Say it

    What is Newton's method, and why isn't it used to train deep networks?

    Say your answer out loud

    Aim for 30 seconds. It feels different from reading it, and that's the point.

    Tick what you covered

    The interviewer pushes further

    Follow-up 1 of 3

    Why does Newton's method have no learning rate?

    Answer it out loud, then check.

    The Hessian scales each direction by its curvature, so it already knows how far to go in the quadratic model. A natural step size is 1. In practice, damping or a line search reduce it when the approximation isn't trustworthy, particularly far from the solution.

    Follow-up 2 of 3

    Why might Newton's method be attracted to saddle points?

    Answer it out loud, then check.

    It solves for where the gradient is zero, and a saddle has zero gradient too. With a negative curvature direction, the step can go towards the saddle instead of away. Gradient descent doesn't have this attraction. Damping or using absolute curvature can help.

    Follow-up 3 of 3

    How does XGBoost use second derivatives?

    Answer it out loud, then check.

    It approximates the loss with a second-order Taylor expansion around current predictions. Each example gives a gradient and a Hessian, and these determine leaf values and how good a split is. It makes the same procedure work for many losses, and it's cheap because the Hessian is per example, not per weight.

    Newton's method jumps to the minimum of the local quadratic, using w minus H inverse g. It accounts for curvature, so it needs no learning rate, and converges very quickly near a solution. It's not used for deep networks for three reasons. With n weights, the Hessian takes n squared memory and n cubed to solve. It can move towards saddle points, since it finds any flat point. And mini-batch curvature is noisy. So we use first-order methods. L-BFGS approximates it using recent gradients, and it works well on convex problems. XGBoost also uses second derivatives per example.

    Key terms and sources

    Newton's step, why it handles ill-conditioning, its cost, quasi-Newton methods like L-BFGS, and where second-order ideas are used in ML, such as XGBoost.

    Sources

    Explanations are ours, built from these sources. Lab numbers are illustrative, and worked examples were checked by calculation.