Unit 5.5 · about 4 h
84 / 324Newton and quasi-Newton methods
Second-order methods show what curvature information can buy and what it costs. This optional unit separates fast local convergence from an unjustified global guarantee.
- derive
You can now
- Derive the Newton step from a quadratic model and explain when it is a descent direction.
- Prove a local quadratic error recurrence and identify the smoothness, nondegeneracy and starting-point assumptions.
- Compare Newton with a quasi-Newton solver using stationarity residuals and separate function, gradient and Hessian evaluation counts.
Covers
- Newton and quasi-Newton methods
Study, in this order
3 steps
- Newton's model, line search and convergenceConvex Optimization
Sections 9.5.1 to 9.5.3 (pp. 484 to 491), and the Summary on p. 496
Depth · Read the step, decrement and proof assumptions; follow the quadratically convergent phase argument on pp. 490 to 491. Skip 9.5.4's large numerical examples and 9.6.
- Newton as rootfindingFundamentals of Numerical Computation
Section 4.3.1, equations 4.3.3 to 4.3.8, and Section 4.3.2's
newtonalgorithmDepth · Apply the rootfinding argument to the objective's derivative. Inspect the stopping conditions rather than treating small successive steps as a certificate.
- A quasi-Newton comparison with an analytic gradientSciPy minimize: BFGS
BFGS method; options
gtol,maxiter,c1,c2andhess_inv0; Notes on precision lossDepth · Use the default line-search parameters and initial inverse-Hessian approximation. Do not study or implement a full BFGS convergence proof here.
Focus on
- Minimizing the local quadratic model gives \(Hp=-g\). Solve this system instead of forming \(H^{-1}\). Positive definite \(H\) makes \(g^\top p<0\) for nonzero \(g\); an indefinite Hessian does not.
- A Lipschitz Hessian and a uniformly bounded inverse Hessian near a nondegenerate minimizer give a quadratic error bound for full Newton steps, once the starting point is close enough. Backtracking handles the approach to that neighborhood.
- Quasi-Newton methods replace freshly evaluated curvature with an approximation informed by gradient changes. Their iteration count alone hides line-search evaluations; BFGS is an oracle here, not a second implementation assignment.
Reproduce closed-book
float64 for four updates: absolute errors after each are 0.1290322581, 0.01124439868, 9.394478985e-5 and 6.618699366e-9. Compare each displayed error with absolute tolerance 1e-10. The first four ratios \(|e_{\text{next}}|/e^2\) are 0.516129, 0.675367, 0.743020 and 0.749941, approaching 3/4; stop the rate measurement before rounding dominates. With SciPy 1.18.1, call minimize on the same scalar objective with x0=np.array([1.5],dtype=np.float64), jac returning np.array([x[0]**3+x[0]-2],dtype=np.float64), method='BFGS', options={'gtol':1e-10,'maxiter':100}. It reports success, eight iterations, nine function and nine gradient evaluations, and gradient infinity norm 1.32e-13. Require \(|x-1|\le 10^{-9}\) and \(\|\operatorname{grad}\|_\infty \le 10^{-10}\); compare work at that residual, counting Newton's derivative and Hessian calls too. Do not infer a timing advantage. No random draws are needed.Traps
- Applying the rootfinding Newton formula to \(\phi\) rather than \(\phi'\). That finds a zero of the loss, not its stationary point.
- Claiming quadratic convergence at a multiple root, or from every starting point. A vanishing derivative breaks the local denominator bound.
- Counting BFGS iterations while ignoring its line-search calls, or interpreting solver success without checking the returned gradient.
Practice
FNC Python: multiple-root Newton convergence
Exercise 4.3.7, parts (a) and (b)
Attempt the repeated-root derivation before reading the nearby convergence discussion. For part (b), use float64 and separate errors from residuals; do not fit a convergence rate to the final roundoff plateau.
Self-test
-
Why does this example converge to 1 from 1.5?
For \(x>1\), the recurrence gives \(e_{\text{next}}>0\). Also \(e_{\text{next}}/e=(x-1)(2x+1)/(3x^2+1)<1\) because the denominator minus the numerator is \(x^2+x+2>0\). The iterates decrease and stay above 1; their limit must solve \(x^3+x-2=0\). Positive Hessian makes that root unique. Dividing the recurrence by \(e^2\) gives the limit 3/4. -
Where are the local Newton proof assumptions used?
A Lipschitz Hessian bounds the Taylor remainder by a constant times \(\|e\|_2^2\). Nonsingularity and local inverse bounds keep solving with \(H\) from amplifying it without limit. A sufficiently close start keeps the iterates in that neighborhood; full steps give the Newton error cancellation. -
What happens to Newton rootfinding for \(F(x)=(x-r)^2\)?
For \(x\ne r\) the update is \(x_{\text{next}}=x-(x-r)/2\), so \(e_{\text{next}}=e/2\): linear, not quadratic. The simple-root assumption fails because \(F'(r)=0\). -
Must a Newton direction descend at a stationary saddle?
No. At a stationary point \(g=0\), the Newton step is zero when the Hessian is invertible, even if the point is a saddle. Away from it, an indefinite Hessian can also give a non-descent direction.
Completion criterion
Stop when
You can derive the error recurrence, name every local assumption, and explain the Newton/BFGS comparison without treating iteration count or a roundoff plateau as a speed or rate proof.
Mark passed, then open 5.6 Only mark this when you can do it without notes.Leads to
- 2.3 Logistic regression and stable binary cross-entropy Recognize the curvature and stationarity checks behind iterative logistic solvers.
Resources for this unit
- Convex Optimization Read Chapters 1-5 and 9 with the course; use Chapter 10 only for equality-constrained Newton steps.
- Fundamentals of Numerical Computation Study §§1.1-1.4, 2.7-2.8, 3.2-3.4 and 4.2-4.3 for floating point, conditioning, stability, least squares and iteration error, in the Python edition.
- SciPy minimize: BFGS Read the BFGS method description and
gtol,maxiter,c1andc2options. Supply an analytic gradient and compare residuals and evaluation counts, not just iterations.
Also in this section
- Stanford EE364a - Convex Optimization Follow lectures 1-9 and 15-16; use lecture 17 only for KKT systems. Leave full interior-point treatment for later.
- D2L - Optimization Algorithms Use the convexity, GD, SGD, minibatch, momentum, AdaGrad, RMSProp, Adam and scheduler sections for ML derivations and code.
- CVXPY basic and DCP tutorials Use as the solver oracle after deriving a constrained problem and its KKT conditions by hand.
- Proximal Algorithms Read Sections 1.1, 4.2 and the elementwise soft-thresholding formula in 6.5.2, then the lasso formulation on p. 196. Skip 7.1.1's penalty-scaling and Gram-rewrite errors on p. 197; derive the update from 4.2 and 6.5.2.
- PyTorch optimizer and gradient-clipping contracts Use AdamW's algorithm and
clip_grad_norm_'s parameters to locate weight decay and clipping precisely. Inspectstate_dictfor optimizer restart; no network training is assigned. - PyTorch numerical type information Read
torch.finfo'seps,maxandsmallest_normalfields and its subnormal note; inspectfloat64,float32,float16andbfloat16on CPU. - The Accuracy of Floating Point Summation Read Section 2's recursive-sum error bound and Section 3's pairwise and compensated summation algorithms. Leave the statistical error models and historical machine details aside.
- Accurately computing running variance Read the Welford mean and centered-sum recurrences. Prove the centered-sum invariant and translate the recurrence to NumPy; skip the C++ class.