Empirical Risk Minimization

How it works

1. D is known: x is uniform over n points in [0, 1] and its label is a target rule f (a threshold or an interval), flipped with probability η; so every L_{_D}(h) can be computed exactly.
2. Draw S ∼ D^{^m}: m independent labelled examples from a seeded random stream.
3. For every h in H (thresholds or intervals on a grid, listed in order), count its mistakes on S to get L_{_S}(h), and compute its true risk L_{_D}(h) from D. For the class of all functions, ERM simply memorises S: the majority label at each seen point, 0 elsewhere.
4. ERM returns h_{_S}, the first hypothesis with the smallest L_{_S}. Compare L_{_S}(h_{_S}) with L_{_D}(h_{_S}), and split L_{_D}(h_{_S}) into ε_{_app} = min over H of L_{_D}(h) plus ε_{_est} = L_{_D}(h_{_S}) − ε_{_app}.
5. Repeat with R fresh samples and count how often L_{_D}(h_{_S}) > ε_{_app} + ε. The finite-class bound says m ≥ (ln(|H|/δ))/ε (realizable, c = 1) or m ≥ 2 (ln((2|H|)/δ))/ε^{^2} (agnostic, c = 2) keeps that frequency at most δ.
6. Run the same samples through richer and richer classes: ε_{_app} falls, the average ε_{_est} rises, and memorising (all 2^{^n} functions) reaches small L_{_S} with a large L_{_D}.

Default run (16 steps): D: x uniform over 20 points in [0, 1], label f(x) = 1[x >= 0.4] flipped with probability η = 0.1. H = thresholds on the grid i/10, |H| = 11. The learner never sees D; it gets S ~ D^{^m} with m = 20. … Richer classes on the same 200 samples: ε_app falls from 0.42 (thresholds, k = 1) to 0.1 (all functions), while the average ε_est rises to 0.2282 for all functions (average L_{_S} 0.0617). Lowest average L_{_D}(h_{_S}): thresholds, k = 5 (0.1136).