One sample, and every hypothesis at once. Bernoulli promises the training error of a fixed rule tracks its true error — but you chose your rule after seeing the data, so that promise is void. Vapnik & Chervonenkis fixed it: if the gap between training and true error is small uniformly over the whole class, then the one you pick is safe. The engine builds that guarantee live — per-hypothesis tail, union over the class, and the measured worst deviation — from the four-line inequality. The blue team builds and defends it; the red team tries to break it.
source V. N. Vapnik & A. Y. Chervonenkis, On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities, Theory of Probability and Its Applications, vol. 16 (2), pp. 264–280 (1971) — doi:10.1137/1116025. No stable open preprint of the 1971 translation; author/title/year cited AMBER. Rendered, not quoted.
For one fixed hypothesis, Hoeffding bounds the two-sided gap:
P(|Remp(h) − R(h)| > ε) ≤ 2e−2mε². But that h must be chosen before the sample. A learner picks after — so bound all of them. The union bound charges one Hoeffding tail per hypothesis:
P(suph∈H |Remp−R| > ε) ≤ |H|·2e−2mε². Looser than the single tail by exactly the factor |H| — no independence assumed. Live for the current controls:
| quantity | value |
|---|
This sphere is the-hoeffding-bound summed over every rule at once. One tail bounds one hypothesis; the union of tails bounds the supremum — and a supremum bound is what makes the-empirical-risk-minimization trustworthy.
Because the gap is small for every h, it is small for the data-chosen ĥ too. That is why minimizing training error is a valid proxy for minimizing true error — each sphere is the next one's premise.
The blue team's live check: re-run the fixed-seed Monte Carlo, re-derive the bounds, and confirm the measured sup-deviation frequency stays under the applied bound. If red drops the |H| factor, this badge catches it.
The guarantee needs four things fed in:
| symbol | what | here |
|---|---|---|
| |H| | size of the finite hypothesis class | you set it |
| m | number of i.i.d. training examples | you set it |
| ε | tolerance on the train/true gap | you set it |
| ℓ ∈ {0,1} | bounded loss (Hoeffding's only demand) | Bernoulli, R(h)=½ |
Worst-case true risk R(h)=½ maximizes the deviation, so the test is honest-hard. All hypotheses share the same sample — the union bound needs no independence between them.
Monte Carlo: 4000 fixed-seed samples, sup of |Remp−R| over the class measured each time; the exceedance frequency is what the bound must cover.
Change any control — the tails, the union, and the measured supremum are all recomputed on the spot, never looked up.
What the machine proves: for any finite H and bounded loss, the empirical worst-case gap is covered by the closed-form union bound 2|H|e−2mε² — and therefore the selected ĥ is within ε of its true risk. Invert it and m examples buy uniform accuracy ε for the whole class.
The blue team's witness (left) confirms the coverage live; the red team (right) tries to make the bound lie.
The real theorem of Vapnik & Chervonenkis replaces the raw count |H| with the growth function / VC dimension — the number of distinct labelings the class can produce on m points, which stays polynomial even when |H|=∞. Rademacher complexity tightens it further. This engine renders the finite-class first step, honestly labelled as such — not the full VC bound.
"Training error estimates true error." Cut. Only for a hypothesis fixed before the sample. For the one you selected, a plain Hoeffding bound is invalid — you need the uniform (union) version.
"The union bound needs the hypotheses independent." Cut. P(∪ Ai) ≤ Σ P(Ai) holds for any events. Independence is never used — that is its whole virtue here.
"Bigger |H| just means a bigger constant." Kept, corrected. It costs a log|H| in the sample size (invert the bound), so the class size is a real price, paid in data — the seed of capacity control.
The red team's move: apply the single-h Hoeffding bound to the data-chosen ĥ — drop the |H| union factor so the bound looks tighter. The sup-over-H deviation then breaches it. The witness (window 7) is watching.
Charge only one tail for the selected hypothesis and the applied bound falls below the measured exceedance — the witness recomputes, the guarantee reads BREACHED, and it turns red. Nothing is faked; the attack is real and it is caught.