Project 30: Numerical Stability and Conditioning Lab

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Expert
  • Time: 2-3 weeks
  • Language: Python with NumPy
  • Prerequisites: Projects 1, 20, 26, and 28-29
  • Source: ML-Math P24

What You Will Build

Build a stress laboratory that runs mathematically equivalent formulas across benign and adversarial inputs, measures their disagreement, and explains the failure mechanism. Include catastrophic cancellation in the quadratic formula and finite differences, overflow/underflow in exponentials and probabilities, unstable summation, variance formulas, nearly singular linear systems, and integration/root-finding tolerances. Implement stable alternatives such as a cancellation-resistant quadratic formula, logsumexp, Welford variance, pairwise or compensated summation, scaling, and residual-based checks. Generate condition estimates by perturbing inputs and measuring relative output change. Each experiment should distinguish problem conditioning from algorithmic stability: sometimes no implementation can recover information the input has already lost.

Real World Outcome

The lab produces an HTML/Markdown report with tables of naive versus stable answers, relative/absolute error, perturbation amplification, runtime, and a diagnosis. A heatmap for a nearly singular matrix or polynomial shows regions where small input changes cause large output changes, while regression tests preserve every discovered counterexample.

Core Question

When a computation returns a wrong-looking answer, is the mathematical problem inherently sensitive, or did the chosen algorithm unnecessarily amplify ordinary floating-point error?

Concepts You Must Understand First

  1. Floating-point model: numbers have finite precision, range, rounding, and special values; machine arithmetic is not real arithmetic.
  2. Forward and backward error: ask whether the answer is close, or whether it exactly solves a nearby problem.
  3. Conditioning: relative input perturbations may be amplified by the problem itself. See Trefethen and Bau, Numerical Linear Algebra.
  4. Cancellation and scale: subtracting close values destroys significant digits; overflow can occur before a ratio becomes small.
  5. Residuals: a small residual helps validate equations but must be interpreted with scale and condition.

Build Milestones

  1. Build a reproducible experiment harness using float32/float64 and high-precision or symbolic references.
  2. Add cancellation, summation, variance, exponential/probability, derivative, root, and integration cases.
  3. Add ill-conditioned matrix systems and empirical perturbation-based condition estimates.
  4. Implement stable counterparts and explain why each rewrite helps.
  5. Export a ranked report and preserve minimal adversarial inputs as regression tests.

Hints in Layers

  1. Use decimal or mpmath only as a reference oracle, not as the “fix” for every algorithm.
  2. Sweep input magnitude logarithmically and report both relative and absolute error.
  3. To separate conditioning from stability, compare several algorithms against the same high-precision problem and perturb the exact inputs independently.

Common Pitfalls and Debugging

  • Symptom: relative error is infinite near zero. Cause: the denominator is meaningless at that scale. Fix: report absolute error or a mixed tolerance.
  • Symptom: softmax becomes NaN. Cause: exponentials overflow. Fix: subtract the maximum before exponentiation and use log-domain computations.
  • Symptom: solver residual is tiny but solution varies wildly. Cause: the system is ill-conditioned. Fix: report condition estimate and perturbation sensitivity alongside residual.

Definition of Done

  • The suite contains at least six distinct numerical failure families.
  • Every experiment has a trusted reference and deterministic input generation.
  • Stable alternatives materially improve error on documented adversarial cases.
  • Reports distinguish conditioning, algorithmic instability, and tolerance mistakes.
  • Float precision and input scale can be swept reproducibly.
  • Counterexamples become regression tests with clear diagnostic assertions.

Previous: Project 29 · Complete learning path · Next: Project 31