Newton's Method and BFGS

Newton uses local curvature to pick both direction and step length, and BFGS rebuilds that curvature from past gradients so the step stays affordable.

On f of x equals x squared plus 2x plus 5, Newton starts at 2 with slope 6 and curvature 2 and jumps straight to minus 1, while BFGS rebuilds that curvature from past gradients

Why Does This Exist?

Gradient descent knows the slope but not the shape. In a narrow valley it zigzags, and on a flat plateau it crawls, because one shared step size cannot suit every direction. The fix is curvature: fit a local quadratic, then jump to its minimum in one move.

That move is Newton's method. It converges very fast near a minimum but pays for the Hessian and its solve on every step. BFGS keeps the idea and drops the bill by rebuilding curvature from the gradients already seen, which is why limited-memory BFGS still optimizes medium models and scientific losses today. The optimality picture sits in optimality conditions, the convex setting where the quadratic model is trustworthy sits in convex optimization, and the behavior-space cousin sits in natural gradient.

The one idea you need first

A Hessian is the matrix of second derivatives. It says how fast the slope itself turns in each direction. Write $H$ for that matrix, $g$ for the gradient vector, and $s$ for a step. Newton solves $H s = -g$ and then moves by $s$ . When $H$ is positive definite, that $s$ points downhill with a length the curvature chose.

Think of It Like This

Skiing by feel against skiing with a contour map

A skier who only feels the slope under their boots picks a direction but must guess how far to glide. Too short wastes runs, too long overshoots the dip and climbs the far wall.

Give that skier a contour map of the bowl. One glance shows both the fall line and how tightly the bowl curves, so the glide length picks itself: short where the bowl bends hard, long where it opens flat. Newton skis with the map. BFGS sketches the map from remembered slopes at each turn, which is cheaper than surveying the whole bowl and close enough to glide well.

Where the picture stops: real losses are not bowls everywhere, and a quadratic map drawn at a saddle points at the wrong place entirely.

How It Actually Works

At $x_{k}$ , replace the loss $f$ with its second-order Taylor model and minimize that model:

x_{k+1} = x_{k} - H_{k}^{-1} g_{k}

Here $H_{k}$ is the Hessian at $x_{k}$ and $g_{k}$ the gradient there. On a quadratic the model is exact, so the method lands on the minimum in one step. Near a smooth minimum it converges quadratically, roughly doubling correct digits per step once close.

BFGS never forms $H$ . It keeps an approximation $B_{k}$ updated from the step $s_{k} = x_{k+1} - x_{k}$ and the gradient change $y_{k} = g_{k+1} - g_{k}$ so that $B_{k+1} s_{k} = y_{k}$ , called the secant condition. L-BFGS stores only the last few $(s, y)$ pairs and applies $B^{-1} g$ through two loops, which costs linear memory in the parameter count.

Worked example

Take $f(x) = x^{2} + 2x + 5$ starting at $x_{0} = 2$ .

Gradient: $g(x) = 2x + 2$ , so $g(2) = 6$ . Hessian: $H = 2$ everywhere. Newton step:

x_{1} = 2 - 6 / 2 = 2 - 3 = -1

Check: $f(2) = 4 + 4 + 5 = 13$ . At $x = -1$ , $f(-1) = 1 - 2 + 5 = 4$ and $g(-1) = -2 + 2 = 0$ , so this is the stationary point, and $H = 2$ positive confirms a minimum. One step done, because the quadratic model was the function itself.

The secant pair for BFGS is $s = -1 - 2 = -3$ and $y = 0 - 6 = -6$ . Ratio $y / s = 2$ recovers the true curvature $H = 2$ exactly here. A gradient step with size $0.1$ would have moved only to $2 - 0.6 = 1.4$ with loss $1.96 + 2.8 + 5 = 9.76$ , still far from $4$ .

Code

The snippet below takes the Newton step computed by hand and compares it with one small gradient step.

1def f(x: float) -> float:2    return x**2 + 2 * x + 53
4
5def grad(x: float) -> float:6    return 2 * x + 2  # derivative of x^2 + 2x + 57
8
9x0 = 2.010h = 2.0  # constant Hessian for this quadratic11x_newton = x0 - grad(x0) / h  # exact curvature step12x_grad = x0 - 0.1 * grad(x0)  # one small first-order step13print(round(x_newton, 3))  # -> -1.014print(round(f(x_newton), 3))  # -> 4.0 minimum in one jump15print(round(x_grad, 3))  # -> 1.4 still far away

Newton lands on $-1.0$ with loss $4.0$ . The gradient step reaches only $1.4$ .

Watch Out For

Trusting the quadratic model far from a minimum

Newton minimizes the local quadratic, not the loss. Where the Hessian has negative curvature, that quadratic opens downward along some direction and its minimum sits at a saddle or a maximum, so the raw step can climb or diverge.

Symptom: loss jumps up, parameters blow past sensible bounds, or iterates stick at a saddle with zero gradient. Fix: never take the raw step globally, add a line search or trust region, and shift indefinite Hessians toward positive definite before solving.

Feeding BFGS stale or scaled curvature

BFGS curvature comes from history, so rescaled parameters, restarted runs, or noisy stochastic gradients poison the $(s, y)$ pairs. The approximation then reports curvature that no longer describes the current bowl.

Symptom: steps shorten to nothing, direction degrades below gradient descent, or L-BFGS restarts help more than extra pairs. Fix: skip pairs with $s^{T} y$ too small, refresh the memory after rescaling, and prefer plain stochastic first-order methods when gradients stay noisy.

The Quick Version

Newton solves $H s = -g$ and steps by $s$ , so curvature picks both direction and length.
On a quadratic it finishes in one step, and near a smooth minimum it converges very fast.
BFGS rebuilds curvature from step and gradient-change pairs, and L-BFGS keeps only recent pairs.
The fixture $f(x) = x^{2} + 2x + 5$ moves Newton from $2$ to $-1$ with loss $13$ to $4$ , while a small gradient step reaches only $1.4$ .
Raw Newton steps need a line search or trust region away from minima.
BFGS needs fresh pairs with positive $s^{T} y$ , or its map goes stale.