Newton, Quasi-Newton and Conjugate Gradient

Newton's method

DefinitionNewton's method

$$x_{t+1} = x_t - \big[\nabla^2f(x_t)\big]^{-1}\nabla f(x_t).$$

Equivalently: minimise the second-order Taylor model of $f$ at $x_t$ exactly, rather than the quadratic upper bound of the descent lemma.

TheoremLocal quadratic convergence

Let $f$ be twice differentiable with $\nabla^2f$ being $M$-Lipschitz, and let $x^\star$ satisfy $\nabla f(x^\star)=0$ and $\nabla^2f(x^\star)\succeq\mu I$ with $\mu>0$. Then there is $r>0$ such that whenever $\norm{x_t-x^\star}_2\le r$,

$$\norm{x_{t+1}-x^\star}_2 \le \frac{M}{\mu}\norm{x_t-x^\star}_2^2 .$$

ProofReveal

PropositionAffine invariance

Let $T$ be invertible and $\tilde f(z) = f(Tz)$. If $\tilde x_t = T^{-1}x_t$ then the Newton iterates of $\tilde f$ from $\tilde x_0$ satisfy $\tilde x_t = T^{-1}x_t$ for all $t$. No such statement holds for gradient descent.

ProofReveal

This is why no condition number appears in the Newton rate and no step size needs tuning: the method does not see the coordinate system. Everything a rescaling could break, it is immune to.

Quasi-Newton: BFGS and L-BFGS

Newton's method needs $\nabla^2 f$ ($O(d^2)$ memory) and a solve ($O(d^3)$ time). Quasi-Newton methods build an approximation $B_t \approx \nabla^2f(x_t)^{-1}$ from gradient differences alone.

DefinitionSecant condition

Let $s_t = x_{t+1}-x_t$ and $g_t = \nabla f(x_{t+1})-\nabla f(x_t)$. A curvature approximation $H_{t+1}\approx\nabla^2f$ should satisfy the secant condition $H_{t+1}s_t = g_t$, which is the exact relation for a quadratic.

PropositionThe BFGS update

The BFGS update to the inverse approximation $B_t \approx H_t^{-1}$ is

$$B_{t+1} = \left(I - \frac{s_tg_t^\top}{g_t^\top s_t}\right)B_t\left(I-\frac{g_ts_t^\top}{g_t^\top s_t}\right) + \frac{s_ts_t^\top}{g_t^\top s_t}.$$

It satisfies $B_{t+1}g_t = s_t$ (the secant condition in inverse form), preserves positive definiteness when $g_t^\top s_t>0$, and is the solution of $\min_B \norm{B - B_t}_W$ subject to $B = B^\top$ and $Bg_t = s_t$ for a particular weighted Frobenius norm.

The variational characterisation is proved in Nocedal–Wright and is quoted here. Two consequences matter:

• $g_t^\top s_t > 0$ is a curvature condition; it holds automatically for strongly convex $f$ and must be enforced by a line search otherwise. If it fails, the update is skipped — a detail that matters in practice.
• Each update is a rank-two modification, so applying $B_t$ costs $O(d^2)$ rather than $O(d^3)$.

1. State. The last $m$ pairs $(s_i, g_i)$, typically $m \in [5,20]$. Never form $B_t$.
2. First loop (newest to oldest): $q \leftarrow \nabla f(x_t)$; for each $i$, set $\alpha_i = \rho_i s_i^\top q$ with $\rho_i = 1/(g_i^\top s_i)$, then $q \leftarrow q - \alpha_i g_i$.
3. Scale. $r \leftarrow \gamma q$ with $\gamma = (s_{\text{last}}^\top g_{\text{last}})/(g_{\text{last}}^\top g_{\text{last}})$.
4. Second loop (oldest to newest): $\beta = \rho_i g_i^\top r$, then $r \leftarrow r + (\alpha_i - \beta)s_i$.
5. Return $-r$ as the search direction; take a line search along it.

Cost per iteration: $O(md)$ time and memory. That is the whole reason L-BFGS is the default general-purpose optimiser for smooth deterministic problems of moderate size.

Conjugate gradient

TheoremConjugate gradient minimises over Krylov subspaces

For $f(x) = \tfrac12x^\top Ax - b^\top x$ with $A\succ0$, the conjugate gradient iterates satisfy

$$x_t = \argmin\Big\{f(x) : x \in x_0 + \operatorname{span}\{r_0, Ar_0,\dots,A^{t-1}r_0\}\Big\}, \qquad r_0 = b - Ax_0,$$

and consequently

$$\frac{\norm{x_t-x^\star}_A}{\norm{x_0-x^\star}_A} \le 2\left(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\right)^t ,$$

with exact termination at $t = d$ in exact arithmetic, and at $t =$ (number of distinct eigenvalues) in general.

Quoted from Nocedal–Wright / Trefethen–Bau. Note the rate is the same $\sqrt\kappa$ as acceleration — and for good reason: CG solves the optimal-polynomial problem exactly, adaptively, and acceleration solves it with a fixed schedule. CG is the accelerated method for quadratics; Nesterov's contribution was extending the rate to general convex functions.

Why these are rare in deep learning

Empirical observationSecond-order methods are rarely used at scale

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

Adam and SGD with momentum dominate deep learning; L-BFGS and Newton-type methods do not, despite their superior rates on the problems where those rates apply.

Problems

Local quadratic convergence of Newton's methodProof · Advanced · 1 hour Newton's method is affine invariantProof · Intermediate · 30 min Conjugate gradient and Krylov optimalityProof · Advanced · 1 hour The BFGS update satisfies the secant conditionProof · Advanced · 30 min