From slope to curvature: why one more derivative changes everything
The previous guide left gradient descent zig-zagging down a long, thin valley. The diagnosis was sharp: the gradient points downhill, but on an ill-conditioned problem 'downhill' is almost perpendicular to the direction you actually need to travel, so the iterates bounce off the valley walls and crawl along the floor. Gradient descent only ever knows the slope — the first derivative. The fix in this guide is to also feed it the curvature — the second derivative — so it can tell a gentle valley from a steep one and scale its step accordingly. That single extra piece of information is what turns crawling into striding.
In one dimension the idea is pure Newton's method, just aimed at the right target. To minimize a smooth f(x) you want the place where the slope vanishes, f'(x) = 0 — that is the first-order optimality condition you met in the rung's first guide. So apply root-finding Newton not to f but to f': replace f by f' and f' by f'' in the familiar iteration. The single-variable update becomes x_{n+1} = x_n - f'(x_n)/f''(x_n). You are no longer chasing a zero of the function; you are chasing a zero of its derivative, which is exactly a flat spot — a candidate minimum.
Newton's step in many variables: the Hessian as a local map
Now lift it to many variables, where x is a vector. The slope becomes the gradient g — the vector of partial derivatives, pointing uphill — and the curvature becomes the Hessian H, the matrix of all second partial derivatives. The scalar division by f'' becomes solving a linear system: the Newton step s solves H s = -g, and you update x_{n+1} = x_n + s. Read that as 'divide the negative gradient by the curvature matrix'. The Hessian rescales and rotates the raw downhill direction into the direction that points at the bottom of the local quadratic bowl.
Here is the picture that makes it click. Approximate f near x_n by its second-order Taylor model — a quadratic bowl whose linear part is g and whose curvature is H. The Newton step is exactly the jump to the minimum of that bowl, found in one shot by solving H s = -g. If f really were quadratic, Newton would land on the true minimum in a single step, no matter how stretched the valley. That is the deep reason it cures the zig-zag: where gradient descent sees only steepness and over-steps the narrow direction while under-stepping the long one, Newton sees the whole elliptical shape and steps to the center directly.
given x, gradient g(x), Hessian H(x):
repeat:
g = gradient(x)
H = hessian(x)
solve H s = -g # one linear solve (e.g. Cholesky)
x = x + s # full Newton step
until ||g|| <= tol
# 1-D special case: x = x - f'(x) / f''(x)What it buys, and what it costs
The payoff is the same dazzling speed you saw in root-finding: near a well-behaved minimum, Newton's method converges quadratically, roughly doubling the number of correct digits each step. Three or four iterations can take you from a rough guess to full precision. Crucially, this rate is independent of the conditioning of the valley — the Hessian solve automatically undoes the stretching that crippled gradient descent. A problem with condition number 10^6, on which gradient descent might need millions of steps, can be solved by Newton in a handful. That is the headline.
Now the fine print, and it is substantial. First, you must form the Hessian — for n variables that is an n-by-n matrix of n^2 second derivatives, often painful or impossible to write down. Second, you must solve H s = -g every iteration, costing about O(n^3) work with a direct solve (you factor H, you never form its inverse). For n in the millions — the routine size of a modern neural network — both the n^2 storage and the n^3 solve are flatly unaffordable. Third, like its root-finding cousin, the quadratic rate is only local: from a poor start Newton can overshoot, diverge, or be lured toward a saddle or a maximum, because nothing in H s = -g insists on going downhill.
Quasi-Newton: almost all the speed, none of the Hessian
The Hessian is the expensive ingredient, so the obvious question is: can we get Newton-like steps without it? That is exactly what quasi-Newton methods do. The idea is beautifully thrifty. You never compute H. Instead you keep a running approximation B to the Hessian (or, more cleverly, to its inverse) and improve it for free using information you are already collecting — namely, how the gradient changed from one step to the next. If the gradient shifted by y when you moved by s, then a good curvature model should satisfy the secant condition B s = y, the multivariable echo of estimating a second derivative from two first-derivative samples.
The most celebrated recipe is BFGS. Each step it makes a small, rank-two correction to the inverse-Hessian estimate so the secant condition holds, while staying symmetric and positive-definite (so the step is always a descent direction). Because BFGS updates the inverse directly, each step costs only O(n^2) — matrix-vector work, no n^3 solve and no second derivatives at all, just gradients. The remarkable result: BFGS converges superlinearly, faster than gradient descent's linear crawl and, in practice, nearly as fast as true Newton, yet it never once forms or factors a Hessian.
Even O(n^2) storage is too much when n runs into the millions. The answer is L-BFGS ('limited-memory' BFGS), the version that actually trains large models. It never stores any matrix at all; it keeps only the last few (say 5 to 20) pairs of step-and-gradient-change vectors and reconstructs the action of the approximate inverse-Hessian on the gradient by a clever two-loop recursion. Memory and per-step cost drop to O(n) times a small constant. L-BFGS is the default heavy-duty optimizer in countless scientific and machine-learning libraries precisely because it scales to enormous n while keeping much of Newton's curvature wisdom.
Where this sits, and where it breaks down
Step back and see the ladder of methods, each buying speed with a different currency. Gradient descent uses only the gradient: cheap per step, but linear and conditioning-crippled. Newton uses gradient and full Hessian: quadratic and conditioning-proof, but O(n^2) memory and O(n^3) per step. Quasi-Newton (BFGS, L-BFGS) sits in between by learning the curvature from gradient differences: superlinear, gradient-only, O(n) to O(n^2) per step. Choosing among them is a deliberate trade of per-step cost against number-of-steps — the recurring engineering judgment of this whole rung.
Be honest about the limits. All three are local descent methods: on a non-convex landscape they find a nearby minimum, never a guarantee of the global one — start elsewhere and you may land elsewhere. Every quantity here is computed in floating point, so the gradient, the Hessian solve, and the BFGS update all carry round-off; a near-singular Hessian (a very flat or very stretched minimum) is ill-conditioned and bleeds digits exactly as the floating-point rung warned — accuracy is conditioning times stability, and a stable optimizer still struggles on an ill-conditioned bowl. And the gradients these methods need are usually supplied not by hand but by automatic differentiation, the engine that makes large-scale optimization practical at all.
So why, if L-BFGS is so good, does deep learning not just use it? Because the next guide changes the rules. When the objective is an average over millions of data points, even one exact gradient is too expensive to compute, and we settle for a cheap, noisy gradient from a random mini-batch. That noise quietly poisons the curvature estimates BFGS depends on — the gradient differences are no longer trustworthy curvature signals. The workhorse of machine learning is therefore not Newton or quasi-Newton at all, but stochastic gradient descent with momentum, which is the subject we turn to next.