Newton's Method for OptimizationOpen in Colab

Newton's Method for Optimization

Newton's method minimizes a function by fitting a local quadratic model at the current point and jumping directly to its minimum. For a true quadratic this lands at the global minimum in one step. For non-quadratic functions it converges much faster than gradient descent near a minimum.

The core idea behind Newton's method

Near a point x0\mathbf{x}_0, any smooth ff is approximated by the second-order Taylor expansion:

f(x)≈f(x0)+∇f(x0)⊤(x−x0)+12(x−x0)⊤H(x0)(x−x0)f(\mathbf{x}) \approx f(\mathbf{x}_0) + \nabla f(\mathbf{x}_0)^{\top}(\mathbf{x}-\mathbf{x}_0) + \tfrac{1}{2}(\mathbf{x}-\mathbf{x}_0)^{\top} \mathbf{H}(\mathbf{x}_0)(\mathbf{x}-\mathbf{x}_0)

where H(x0)=∇2f(x0)\mathbf{H}(\mathbf{x}_0) = \nabla^2 f(\mathbf{x}_0) is the Hessian (matrix of second derivatives).

Write the displacement as s=x−x0\mathbf{s} = \mathbf{x} - \mathbf{x}_0. Newton's method minimizes the right-hand side over s\mathbf{s}, ignoring the constant f(x0)f(\mathbf{x}_0).

Deriving the Newton step

Take the gradient of the quadratic model with respect to s\mathbf{s} and set it to zero:

∇s ⁣[∇f(x0)⊤s+12s⊤H s]=∇f(x0)+H s=0\nabla_{\mathbf{s}}\!\Big[\nabla f(\mathbf{x}_0)^{\top}\mathbf{s} + \tfrac{1}{2}\mathbf{s}^{\top}\mathbf{H}\,\mathbf{s}\Big] = \nabla f(\mathbf{x}_0) + \mathbf{H}\,\mathbf{s} = \mathbf{0}

Solve for s\mathbf{s}:

H s=−∇f(x0)  ⟹  s=−H−1∇f(x0)\mathbf{H}\,\mathbf{s} = -\nabla f(\mathbf{x}_0) \;\Longrightarrow\; \mathbf{s} = -\mathbf{H}^{-1}\nabla f(\mathbf{x}_0)

The Newton update is:

  x←x−H−1∇f(x)  \boxed{\;\mathbf{x} \leftarrow \mathbf{x} - \mathbf{H}^{-1}\nabla f(\mathbf{x})\;}

Compare to gradient descent x←x−η ∇f(x)\mathbf{x} \leftarrow \mathbf{x} - \eta\,\nabla f(\mathbf{x}): Newton replaces the scalar learning rate η\eta with the inverse Hessian H−1\mathbf{H}^{-1}, which rescales and rotates the gradient to account for curvature.

Curvature correction

In a steep direction (λi\lambda_i large), H−1\mathbf{H}^{-1} shrinks the step — preventing overshoot. In a flat direction (λi\lambda_i small), it enlarges the step — accelerating progress. Gradient descent uses the same step size everywhere, so it struggles when the loss landscape is elongated (ill-conditioned).

Watch it run

The step computed on the function worked below, with the level sets drawn so you can see where the step points:

Newton's method — one step to the minimum, and why we can't always take it

1/7

f(x, y) = x² + xy + y² − 3x, a convex quadratic whose minimum sits at (2, −1) with f = -3. Start at the origin. The contours are ellipses rather than circles — the xy term tilts them — and that tilt is exactly what a single learning rate cannot cope with.

python
1def newton(f, grad, hess, x, steps):
2 for _ in range(steps):
3 g = grad(x)
4 H = hess(x)
5 s = -solve(H, g) # -H^-1 @ g
6 x = x + s
7 return x
8
9def gradient_descent(grad, x, eta, steps):
10 for _ in range(steps):
11 x = x - eta * grad(x) # same step size
12 return x # in every direction
13
14# f(x, y) = x^2 + x*y + y^2 - 3x
15grad = lambda p: [2*p[0] + p[1] - 3,
16 p[0] + 2*p[1]]
17hess = lambda p: [[2, 1],
18 [1, 2]]
state
the landscape
-1.53.52-2.5minx₀xy
start
x₀ → (0.000, 0.000)f(x₀) → 0.000minimum → (2.000, -1.000)

Newton's method on f(x, y) = x² + xy + y² − 3x from the origin, the quadratic worked above. Watch the y-component of the step: the gradient's is zero, yet the correct move has y = −1, and the Hessian's off-diagonal term is the only thing that knows it. One step lands exactly on the minimum. The final steps run gradient descent on the same function from the same point for comparison, and then state plainly what Newton costs.

What to notice as you step:

  • The gradient's yy-component is zero at the origin, but the correct step's is −1-1. The minimum is at y=−1y = -1 and the gradient has nothing to say about it; the Hessian's off-diagonal term is the only thing that knows xx and yy are coupled. This is the clearest possible statement of what curvature buys.
  • One step, exactly on the optimum, and the gradient there is exactly zero. For a quadratic the second-order Taylor model is the function, so minimizing the model minimizes the function.
  • The comparison step runs gradient descent on the same function from the same point: 22 steps at η=0.3\eta = 0.3, divergence at η=0.7\eta = 0.7, and no η\eta that fixes it — the condition number is only 3 here, and real problems are far worse.
  • The final step is the bill: O(d2)O(d^2) memory, O(d3)O(d^3) per solve, and steps that move uphill wherever the Hessian is not positive definite.

A single step landing exactly on the minimum (f(x,y)=x2+xy+y2−3xf(x, y) = x^2 + xy + y^2 - 3x)

The function f(x,y)=x2+xy+y2−3xf(x, y) = x^2 + xy + y^2 - 3x has a unique minimum at (2,−1)(2, -1) (verified by the Hessian analysis in the multivariable optimization lesson).

Gradient and Hessian at (0,0)(0, 0):

∇f(0,0)=[2(0)+0−30+2(0)]=[−30]\nabla f(0,0) = \begin{bmatrix} 2(0) + 0 - 3 \\ 0 + 2(0) \end{bmatrix} = \begin{bmatrix} -3 \\ 0 \end{bmatrix} H=[∂2f/∂x2∂2f/∂x∂y∂2f/∂y∂x∂2f/∂y2]=[2112]\mathbf{H} = \begin{bmatrix} \partial^2 f/\partial x^2 & \partial^2 f/\partial x\partial y \\ \partial^2 f/\partial y\partial x & \partial^2 f/\partial y^2 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}

(Constant because ff is quadratic.)

Invert the Hessian. For a 2×22 \times 2 matrix:

H−1=1det⁡H[d−b−ca],det⁡H=2⋅2−1⋅1=3\mathbf{H}^{-1} = \frac{1}{\det\mathbf{H}} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}, \qquad \det\mathbf{H} = 2\cdot2 - 1\cdot1 = 3 H−1=13[2−1−12]\mathbf{H}^{-1} = \frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}

Newton step from (0,0)(0, 0):

x1=[00]−13[2−1−12][−30]=−13[−63]=[2−1]\mathbf{x}_1 = \begin{bmatrix} 0 \\ 0 \end{bmatrix} - \frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \begin{bmatrix} -3 \\ 0 \end{bmatrix} = -\frac{1}{3}\begin{bmatrix} -6 \\ 3 \end{bmatrix} = \begin{bmatrix} 2 \\ -1 \end{bmatrix}

Newton lands exactly on the minimum (2,−1)(2, -1) in one step. This is the defining property: for a quadratic, the Taylor model is the function, so minimizing the model is the same as minimizing the function.

Comparison to gradient descent. A plain gradient step from (0,0)(0, 0) with learning rate η\eta:

x1=[00]−η[−30]=[3η0]\mathbf{x}_1 = \begin{bmatrix} 0 \\ 0 \end{bmatrix} - \eta\begin{bmatrix} -3 \\ 0 \end{bmatrix} = \begin{bmatrix} 3\eta \\ 0 \end{bmatrix}

This only moves along the xx-axis regardless of η\eta — it never escapes to y=−1y = -1. Gradient descent would require dozens of iterations (zigzagging due to the off-diagonal coupling in H\mathbf{H}) to converge to (2,−1)(2, -1).

Python
import numpy as np

def f(x, y):
    return x**2 + x*y + y**2 - 3*x

def grad_f(x, y):
    return np.array([2*x + y - 3, x + 2*y])

H = np.array([[2., 1.], [1., 2.]])
H_inv = np.linalg.inv(H)

# Newton step from (0, 0)
x0 = np.array([0., 0.])
g = grad_f(*x0)
x1 = x0 - H_inv @ g

print(f"Starting point:  {x0}   f = {f(*x0):.3f}")   # [0., 0.]   f = 0.000
print(f"Gradient at x0:  {g}")                          # [-3., 0.]
print(f"Newton step:    {x1}  f = {f(*x1):.3f}")      # [2., -1.]  f = -3.000
print(f"Gradient at x1: {grad_f(*x1)}")                 # [0., 0.] — we're at the minimum

# Gradient descent for comparison: many steps needed
lr = 0.1
xgd = np.array([0., 0.])
for i in range(50):
    xgd -= lr * grad_f(*xgd)
print(f"GD after 50 steps: {xgd.round(3)}  f = {f(*xgd):.3f}")   # ≈ [2., -1.]

Newton vs gradient descent: iteration count and cost

MethodSteps to reach ∥∇f∥<10−6\|\nabla f\| < 10^{-6}Cost per step
Gradient descent (η=0.1\eta = 0.1)∼100\sim 100O(d)O(d)
Newton's method11 (quadratic)O(d3)O(d^3) (matrix inversion)

The O(d3)O(d^3) cost to compute and invert H\mathbf{H} is the main limitation: for a neural network with millions of parameters dd, this is completely infeasible. Practical approximations:

  • Quasi-Newton (L-BFGS): builds a low-rank approximation of H−1\mathbf{H}^{-1} from gradient history — O(d⋅m)O(d \cdot m) per step with mm stored vectors.
  • Diagonal approximation (Adam, RMSProp): keeps only the diagonal of H−1\mathbf{H}^{-1}, one number per parameter — O(d)O(d) per step.

Adam as an approximate Newton

Adam maintains per-parameter running estimates of the second moment of the gradient, which approximates the diagonal of the Hessian. Dividing the gradient by second moment\sqrt{\text{second moment}} is a diagonal Newton step, which is why Adam converges faster than vanilla SGD on ill-conditioned loss surfaces.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
Newton's Method for OptimizationGradient Descent Optimize…Multivariable OptimizationGradient DescentEigenvalues and Eigenvect…