Section 5 of 5 · Mathematical Foundations
Optimization & Numerical Methods
Training behavior is controlled by objective geometry, stochastic noise, finite precision and the state carried by the optimizer.
8 units 17 topics 0/8
Units
8 in this section
- 5.1 Convexity, optimality conditions and conditioning derive5 h
- 5.2 Gradient descent, stochastic gradients and momentum derive · implement6 h
- 5.3 Adaptive optimizers, schedules, clipping and stopping derive · implement5 h
- 5.4 Constraints, KKT conditions and proximal methods derive6 h
- 5.5 Newton and quasi-Newton methods derive4 h
- 5.6 Floating point, rounding, overflow and cancellation derive · measure4 h
- 5.7 Stable log-sum-exp, online reductions and mixed precision derive · implement6 h
- 5.8 Residuals, tolerances and iterative-solver error derive · measure3 h
Before moving on
Checkpoint
Implement and compare optimizers on changed geometry, then diagnose one divergence and one finite-precision failure.
Deliberately out of scope
Leave for later
- Interior-point implementation details
- Nonsmooth variational analysis
- Large-scale distributed optimizer design
Resources for this section
Shared by every unit above
- 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.
- Convex Optimization Read Chapters 1-5 and 9 with the course; use Chapter 10 only for equality-constrained Newton steps.
- D2L - Optimization Algorithms Use the convexity, GD, SGD, minibatch, momentum, AdaGrad, RMSProp, Adam and scheduler sections for ML derivations and code.
- 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.
- 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. - 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. - 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.
Apply the section
Mini-project · An optimizer and numerics test bench (12 to 16 h)
Build gradient descent, heavy-ball and AdamW with clipping, schedules and restartable state, a KKT and proximal-gradient pair checked against a solver, and stable reductions. Compare the optimizers on changed geometry against eigenvalue predictions, then diagnose one divergence and one finite-precision failure.
Steps
- Implement gradient descent, heavy-ball and AdamW with norm clipping, an update-indexed schedule and a state object holding parameters, moments, step count and schedule clock. Exit every loop with a status of converged, stagnated, non-finite or iteration cap, and force each status in tests.
- Run all three on ill-conditioned quadratics, once diagonal and once rotated, predicting the gradient-descent rate from the eigenvalues first. Report the gradient norm and objective gap against gradient evaluations and compare with the prediction.
- Diagnose one divergence past the stability limit by projecting iterates onto the eigenvectors and showing only the top mode growing at the predicted factor. Then add minibatch noise to finite-sum least squares and check the gradient covariance and the constant-step plateau against their formulas.
- Check the AdamW moments against their finite geometric sums on a constant gradient. Then match
torch.optim.AdamWon one deterministic quadratic under the same clipped gradients and per-step rates, save and resume mid-run, and use the unclipped full gradient as the stationarity residual. - Solve a changed two-coordinate QP by hand and with CVXPY and Clarabel, recording every KKT residual with solver status. Derive soft thresholding, then check a lasso proximal loop against a closed form on a diagonal case and against a solver residual on the general case.
- Build log-sum-exp, left-to-right, balanced and Kahan sums, and online mean and variance, testing cancellation, large offsets and low-precision storage with higher-precision accumulation against
math.fsumand higher-precision oracles. Diagnose one finite-precision failure end to end and show the repair.
Deliverables
numlab/optim/: optimizers with exit statuses and restartable state, KKT and proximal code, and the reductions.- Tests for rate predictions, the divergence projection, noise checks, the AdamW oracle and resume, KKT residuals, lasso checks and reduction oracles.
notes/optimization.mdwith predictions beside measurements and both failure diagnoses.
Checks
- rubric · Self-grade with the rubric below
Rubric
| Criterion | Pass | Strong |
|---|---|---|
| Descent geometry | Measured gradient-descent rates on diagonal and rotated quadratics are compared with eigenvalue predictions. | Rotation is shown not to change the gradient-descent rate, with the reason, and momentum gains are reported per gradient evaluation. |
| Divergence and noise | The divergent run is traced to the top eigenmode at the predicted factor, and noise covariance and plateau match their formulas. | Exit statuses separate divergent, stagnated and converged runs without manual inspection. |
| Adaptive state | AdamW matches PyTorch within a stated tolerance and resume equals the uninterrupted run. | A test shows restoring parameters without moments or the schedule clock changes the trajectory. |
| Optimality certificates | The QP records every KKT residual with solver status, and the lasso passes its optimality residual. | Residuals carry stated tolerances, and solver success is never accepted without them. |
| Finite precision | Each reduction matches its oracle, and one finite-precision failure is diagnosed and repaired. | The note separates precision lost in storage from precision lost in accumulation. |
Feeds into: Capstone optimizer stability: the optimizer comparison, the divergence diagnosis and the finite-precision failure.