§8.6.2–8.7Conjugate Gradients · BFGS · Optimization Strategies & Meta-Algorithms

§8.6.2 Conjugate gradients

Conjugate gradients conjugate gradients Avoid inverting H by descending H-conjugate directions dₜ = ∇J + βₜdₜ₋₁ (βₜ via Fletcher–Reeves or Polak–Ribière), eliminating steepest descent's zig-zag; ≤ k line searches minimize a k-dim quadratic. Nonlinear CG adds occasional resets. defined in ch. 8 — open in glossary gets Newton-like speed without ever inverting the Hessian. It starts from a flaw in steepest descent: each line search minimizes along the current gradient, but the gradient at the end of a line search is orthogonal to that search direction — so the next step is perpendicular, and on an elongated bowl the path zig-zags, repeatedly undoing progress along earlier directions (fig 8.6):

The fix: choose each search direction to be conjugate to the previous one — so it does not spoil the minimization already achieved:

For non-quadratic neural-net losses, the conjugate guarantees weaken, so nonlinear conjugate gradients restarts periodically along the plain gradient; it often helps to warm up with a few SGD iterations first.

§8.6.3 BFGS and L-BFGS

Quasi-Newton quasi-newton method A second-order method that APPROXIMATES the inverse Hessian rather than computing it exactly (BFGS is the prominent example), gaining Newton-like directions without the O(k³) inversion. defined in ch. 8 — open in glossary methods take a more direct route than CG: rather than avoid the inverse Hessian, they approximate it. BFGS bfgs / l-bfgs Quasi-Newton: iteratively approximate H⁻¹ with a matrix Mₜ refined by low-rank updates (BFGS, O(n²) memory), tolerant of loose line searches; L-BFGS starts M as the identity each step and stores only O(n) recent vectors — the practical variant for large models. defined in ch. 8 — open in glossary maintains a matrix $\boldsymbol{M}_t \approx \boldsymbol{H}^{-1}$, refined by low-rank updates each step, and descends $\boldsymbol{\rho}_t = \boldsymbol{M}_t\boldsymbol{g}_t$ with a line search. Unlike CG, BFGS does not need the line search to be very accurate — but it must store the full $\boldsymbol{M}$, costing $O(n^2)$ memory, hopeless for million-parameter nets. L-BFGS fixes that by never storing $\boldsymbol{M}$: it assumes the previous estimate was the identity and reconstructs the direction from a few recent vectors, at $O(n)$ per step. The four second-order options:

§8.7 Optimization strategies and meta-algorithms

Not every useful technique is a full optimization algorithm. Many are general templates that specialize into algorithms, or subroutines that plug into many different optimizers. The rest of the chapter covers these — batch normalization, coordinate descent, Polyak averaging, pretraining, model design, and continuation methods.

Next: batch normalization, coordinate descent, and Polyak averaging — batch norm & meta-algorithms.