Newton and quasi-Newton methods

Using curvature

Gradient descent only knows the slope. Newton's method also uses the curvature: it replaces $f$ near the current point by the quadratic that has the same value, gradient and Hessian, and jumps straight to that quadratic's minimum. The step is $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$ . On an exactly quadratic function this lands on the minimum in a single step, whatever the condition number. Near the minimum of any smooth function, convergence is quadratic: the error is roughly squared at each step, so the number of correct digits about doubles.

\mathbf w_{k+1}=\mathbf w_k-H(\mathbf w_k)^{-1}\nabla f(\mathbf w_k),\qquad \lVert\mathbf w_{k+1}-\mathbf w^{*}\rVert\ \lesssim\ C\,\lVert\mathbf w_k-\mathbf w^{*}\rVert^{2}

(1)

Newton on e^x − 2xMinimise

f(x)=e^x-2x

, whose minimum is at

x^{*}=\ln2=0.693147

. Here

f'=e^x-2

and

f''=e^x

. From

x_0=0

x_1=0-(-1)/1=1

, then

x_2=1-0.7183/2.7183=0.7358

x_3=0.6940

and

x_4=0.693148

. The errors

0.307,\ 0.0426,\ 0.0009,\ 4\cdot10^{-7}

shrink faster than any fixed factor. In two variables, for

f=(x-1)^2+2(y+2)^2

(3,0)

we have

\mathbf g=(4,8)

and

H=\mathrm{diag}(2,4)

, so the step is

-H^{-1}\mathbf g=(-2,-2)

and one step reaches the minimum

(1,-2)

Newton's method has a price. With $n$ parameters the Hessian has $n^2$ entries and solving with it costs about $n^3$ operations, which is fine for hundreds of parameters and impossible for millions. Far from the minimum, or where $H$ is not positive definite, the Newton step can even point uphill, so practical versions damp the step with a line search. Quasi-Newton methods keep most of the speed without the cost. BFGS builds an approximation of the inverse Hessian from the observed changes $\mathbf s=\mathbf w_{k+1}-\mathbf w_k$ and $\mathbf y=\mathbf g_{k+1}-\mathbf g_k$ , forcing the secant condition $B\mathbf s=\mathbf y$ . It needs only gradients, costs $O(n^2)$ per step and converges superlinearly. L-BFGS stores just the last $m$ pairs, typically 5 to 20, so memory is $O(mn)$ . It is the usual workhorse for smooth calibrations and maximum-likelihood fits, such as the default optimizers in SciPy.

Newton: $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$ ; one step on a quadratic, quadratic convergence near the minimum.
BFGS: learns an inverse-Hessian approximation from gradient differences, so no second derivatives are needed.
L-BFGS: keeps only the last few pairs, so it scales to many parameters.

Newton needs a safeguardPure Newton can overshoot or diverge from a poor starting point. Library implementations add a line search or a trust region, and they fall back to a gradient step when the Hessian is not positive definite. Do not hand-roll a bare Newton loop for a calibration without these.

Lab · what's graded

The first Newton step15 pts
The second Newton step15 pts
A Newton step in two variables15 pts
Steps on a quadratic15 pts
The secant condition15 pts
Methods and ideas10 pts
Why exact Newton is avoided for huge problems15 pts

Using curvature

\mathbf w_{k+1}=\mathbf w_k-H(\mathbf w_k)^{-1}\nabla f(\mathbf w_k),\qquad \lVert\mathbf w_{k+1}-\mathbf w^{*}\rVert\ \lesssim\ C\,\lVert\mathbf w_k-\mathbf w^{*}\rVert^{2}

(1)

Newton on e^x − 2xMinimise

f(x)=e^x-2x

, whose minimum is at

x^{*}=\ln2=0.693147

. Here

f'=e^x-2

and

f''=e^x

. From

x_0=0

x_1=0-(-1)/1=1

, then

x_2=1-0.7183/2.7183=0.7358

x_3=0.6940

and

x_4=0.693148

. The errors

0.307,\ 0.0426,\ 0.0009,\ 4\cdot10^{-7}

shrink faster than any fixed factor. In two variables, for

f=(x-1)^2+2(y+2)^2

(3,0)

we have

\mathbf g=(4,8)

and

H=\mathrm{diag}(2,4)

, so the step is

-H^{-1}\mathbf g=(-2,-2)

and one step reaches the minimum

(1,-2)

Newton: $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$ ; one step on a quadratic, quadratic convergence near the minimum.
BFGS: learns an inverse-Hessian approximation from gradient differences, so no second derivatives are needed.
L-BFGS: keeps only the last few pairs, so it scales to many parameters.

Lab · what's graded

The first Newton step15 pts
The second Newton step15 pts
A Newton step in two variables15 pts
Steps on a quadratic15 pts
The secant condition15 pts
Methods and ideas10 pts
Why exact Newton is avoided for huge problems15 pts

Using curvature

Lab · what's graded

Log in to run your code.

Newton and quasi-Newton methods

Using curvature

Lab · what's graded

Log in to run your code.