Newton's method and the interior point revolution

Gradient descent builds a linear model at the current point and steps along it, with a scalar $\eta$ standing in for everything the model does not know. Newton's method builds a quadratic model instead:

$f(x + v) \approx f(x) + \nabla f(x)^\top v + \tfrac{1}{2} v^\top \nabla^2 f(x)\, v$

Minimising that over $v$ is a calculus exercise. Differentiate, set to zero, and solve:

$v_{\text{nt}} = -\left[\nabla^2 f(x)\right]^{-1} \nabla f(x)$

Notice what replaced the step size. Gradient descent multiplies the gradient by a scalar, shrinking every direction equally. Newton multiplies it by the inverse Hessian, which stretches and rotates: long steps along flat directions, short steps along steep ones, decided separately for each direction at every iteration.

Near the solution, Newton's method satisfies an error recursion of the form

$\|x_{k+1} - x^\star\| \le C \|x_k - x^\star\|^2$

The error is squared each step. In terms of correct decimal digits, that means the count doubles.

Gotcha: This holds only in the local phase, once the iterate is close enough. Started far away, an undamped Newton step can overshoot badly or head uphill, since the quadratic model is only trustworthy nearby. Real implementations run a damped phase first, scaling the step until progress is verified, and switch to full steps once the local criterion is met.

If the function really is quadratic, the model is not an approximation, so Newton lands on the optimum immediately. Compare this with the previous lesson, where gradient descent on $\kappa = 1000$ was still at about 0.45 after a hundred steps.

import numpy as np

A = np.diag([1.0, 1000.0])          # condition number 1000
x = np.array([1.0, 1.0])            # f(x) = 0.5 * x.T @ A @ x

grad = A @ x
step = np.linalg.solve(A, grad)     # the Newton step, inverse Hessian times gradient
x_next = x - step

print(x_next, 0.5 * x_next @ A @ x_next)
# [0. 0.] 0.0

The Hessian here is $A$ itself, so the Newton step is $A^{-1}Ax = x$, landing exactly on zero. The condition number never entered the calculation. That is not a coincidence, and the next step explains why.

Change variables by any invertible linear map, $x = Ty$, and run Newton's method on the transformed problem. The iterates you get are the images under $T$ of the iterates you would have got on the original. The method is affine invariant: it produces the same sequence of points regardless of how the problem is parameterised.

Key idea: Gradient descent is not affine invariant, and its entire dependence on the condition number is a symptom of that. Conditioning is a property of the coordinates you chose. Newton's method effectively chooses its own coordinates at every step, using the Hessian as the metric, so a badly scaled problem and a well scaled one look identical to it.

This is why feature normalisation transforms how gradient descent behaves and does essentially nothing for a Newton-based solver.

Newton's advantage is bought with work per iteration, and the trade is stark.

At $n = 10^9$, which is ordinary for a neural network, an $n \times n$ Hessian cannot be written down, let alone factorised. This is the honest reason deep learning runs on first-order methods: not that curvature would fail to help, but that nobody can afford it.

The middle ground is quasi-Newton methods such as L-BFGS, which build a low-rank approximation of the inverse Hessian from past gradients at $O(n)$ memory.

Everything so far minimised over all of $\mathbb{R}^n$. Real problems have constraints:

$\text{minimise } f_0(x) \quad \text{subject to } f_i(x) \le 0,\; i = 1,\dots,m, \quad Ax = b$

The previous lesson in this path built the machinery for reasoning about such problems: the Lagrangian, the dual, and the KKT conditions that characterise an optimum. What that machinery does not supply is an algorithm. KKT tells you how to recognise a solution; it does not tell you how to walk to one.

The obstacle is that the feasible region has a boundary, and the optimum usually sits on it. A method that steps freely will leave the region; a method that stops at the boundary loses the smoothness Newton depends on.

The interior point idea is to delete the constraints and add a term that makes approaching the boundary expensive. The logarithmic barrier does exactly that:

$\phi(x) = -\sum_{i=1}^{m} \log\bigl(-f_i(x)\bigr)$

Each term is finite while $f_i(x) < 0$, strictly inside the region, and diverges to $+\infty$ as the constraint becomes tight. Now minimise

$t f_0(x) + \phi(x)$

for a positive parameter $t$. This is unconstrained and smooth, so Newton's method applies directly.

Key idea: Small $t$ weights the barrier heavily and pulls the solution toward the middle of the region. Large $t$ weights the true objective and lets the solution press against the boundary where the real optimum lives. The barrier turned a hard wall into a slope Newton can descend.

Let $x^\star(t)$ be the minimiser for a given $t$. As $t$ sweeps from small to large, those points trace a smooth curve through the interior called the central path, ending at the true optimum.

What makes this more than a heuristic is that each point on the path carries its own proof of quality. Boyd and Vandenberghe show that the construction yields feasible dual variables for which the duality gap is exactly

$f_0(x^\star(t)) - p^\star \le \frac{m}{t}$

where $m$ is the number of inequality constraints.

Key idea: That is a certificate, and it is why the duality lesson had to come first. At $t = 10^6$ with $m = 100$ constraints, you are provably within $10^{-4}$ of optimal. Not estimated, not converged-looking. Bounded, by weak duality.

The outer loop moves along the central path; the inner loop is Newton's method solving one smooth unconstrained problem. Warm starting each inner solve from the previous centre is what keeps the total Newton count low.

Newton's method converges quickly near a solution, but the classical analysis depends on constants tied to the coordinate system, which is unsatisfying for a method that is supposed to be affine invariant.

Nesterov and Nemirovski resolved this in 1994 with self-concordance, a condition on how fast a function's third derivative can change relative to its second. Log barriers satisfy it. For a self-concordant function, using the Newton decrement $\lambda$ as the measure of proximity, the analysis gives a clean statement: once $\lambda \le 1/4$, a full Newton step yields $\lambda^{+} \le 2\lambda^2$.

That bound is affine invariant, involves no unknown problem constants, and converts the whole barrier method into a polynomial-time algorithm rather than a procedure that merely works well.

Two separate questions run through this timeline: whether a polynomial-time algorithm exists at all, settled in 1979, and whether one could also be fast in practice, settled in 1984. Simplex remains competitive and is still widely used.

The theory bounds the work. What surprises people is the empirical behaviour.

This is why a convex problem with a million variables is a scheduling exercise rather than a research project.

Modern solvers refine all of this. Primal-dual interior point methods work on the primal and dual iterates together rather than following the central path exactly, and they exploit sparsity so the $O(n^3)$ factorisation cost applies to structure rather than to raw dimension.

The honest boundary is worth stating plainly. These guarantees are guarantees about convex problems. Point an interior point solver at a nonconvex objective and the barrier still keeps you feasible, Newton still converges to something, and the certificate is gone: $m/t$ bounds the gap to the local optimum only, and weak duality no longer closes.

That is the arc of this path. Convexity said a global optimum exists and can be certified. Duality supplied the certificate. Newton made the steps cheap enough to be worth taking, and the barrier let them reach a constrained boundary. None of it survives the loss of the first assumption.