Project 55: Statistical Learning and Generalization-Bounds Lab

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

  • Difficulty: Level 4: Expert
  • Time: 2 weeks
  • Language: Python
  • Prerequisites: Projects 37, 41, 52, and 54
  • Source: generalization-bounds portion of ML-Math P27, begun in Project 52

What You Will Build

Build a controlled experimental lab that compares empirical train/test gaps with theoretical concentration and capacity-based bounds. Generate or load classification problems, define nested hypothesis classes such as bounded linear predictors and decision trees of increasing depth, and estimate empirical risk over repeated samples. Compute Hoeffding-style fixed-hypothesis bounds and at least one class-capacity bound or defensible proxy, then vary sample size, class complexity, regularization, confidence level, and data noise. The report must show when a bound is valid but loose, when assumptions fail, and why observing one split does not establish generalization.

Real World Outcome

A reproducible sweep produces learning curves, observed generalization gaps, bound curves, violation-frequency checks over many trials, and a table of assumptions. For each configuration, the report states whether the bound covered the observed gap, how loose it was, and what complexity/sample-size tradeoff explains the result.

Core Question

How can finite training performance support a claim about unseen data, and what price do model capacity and confidence demand?

Concepts You Must Understand First

  • Empirical versus population risk and hypothesis classes.
  • Concentration inequalities such as Hoeffding’s inequality — Understanding Machine Learning by Shalev-Shwartz and Ben-David.
  • Uniform convergence, supremum deviations, and the distinction from pointwise convergence — Project 52.
  • Capacity measures: finite-class union bounds, VC dimension, or empirical complexity proxies.
  • IID sampling assumptions, confidence parameters, multiple trials, and selection bias.

Build Milestones

  1. Implement repeated seeded sampling and empirical/population-risk estimates on a distribution with known test behavior.
  2. Add a fixed-hypothesis concentration bound and verify its claimed failure frequency across trials.
  3. Add nested model classes and a capacity-aware bound or clearly labeled empirical proxy.
  4. Sweep sample size, complexity, noise, and regularization; plot gaps and bounds together.
  5. Produce an assumption ledger and examples of valid-but-vacuous and invalidly-applied bounds.

Hints in Layers

  1. Begin with bounded 0/1 loss; many simple concentration formulas require bounded variables.
  2. Use a large independent evaluation sample as an approximation to population risk and label it honestly.
  3. A bound above one for classification can be mathematically valid but practically vacuous—show that explicitly.

Common Pitfalls and Debugging

  • Bound is violated far more than its confidence permits: assumptions, constants, or repeated-selection effects are wrong. Freeze the hypothesis before evaluation and test the simplest case.
  • Bound improves when model class grows: capacity term has the wrong sign or class size. Unit-test monotonicity with synthetic class counts.
  • One successful trial is presented as proof: coverage is probabilistic. Run many independent trials and compare empirical violation rate with delta.

Definition of Done

  • Fixed-hypothesis and class-level guarantees are clearly distinguished.
  • Bound implementation passes analytic sanity and monotonicity tests.
  • Repeated trials measure coverage/violation frequency against claimed confidence.
  • Sweeps reveal sample-size, complexity, noise, and regularization effects.
  • At least one vacuous bound and one broken-assumption case are explained.
  • Every chart states loss range, hypothesis class, sampling assumptions, and confidence.

Previous: Project 54 · Complete learning path · Next: Project 56