Empirical Risk Minimization
Try it: Empirical Risk Minimization
How ERM picks the hypothesis in a finite class H with the smallest empirical risk L_S(h) on a random sample S ~ D^m, how far its true risk L_D(h_S) can be from L_S, how often ERM misses ε over many samples compared with the finite-class sample-complexity bounds, and how a richer class trades approximation error for estimation error until memorising the sample overfits.
How it works
- 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.
- Draw S ~ D^m: m independent labelled examples from a seeded random stream.
- 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.
- 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.
- 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|/δ)/ε² (agnostic, c = 2) keeps that frequency at most δ.
- 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).
Simplified: A toy domain of 8-40 equally likely points on a line, a target that is a threshold or an interval, and symmetric label noise, so L_D is an exact finite sum rather than an integral over a continuous distribution. Hypotheses are thresholds or intervals with endpoints on a grid i/k, or all functions on the n points. ERM ties are broken towards the first hypothesis in listing order (for all functions: towards label 0), where the textbook allows any minimiser. Failure frequencies come from at most 400 seeded samples, so they estimate the probability rather than compute it; the bounds use the natural logarithm.
Loading the simulation…