Theorem Statement
Assumptions
- iid samples from D
- bounded loss in [0,1]
- finite hypothesis class H
Proof Sketch
For each fixed hypothesis, Hoeffding controls the gap between empirical and population risk. Apply the finite union bound over H, then solve the tail probability for epsilon. The whole proof depends on iid sampling, bounded loss, and a finite hypothesis class.
Proof Obligations
Finite class and bounded iid losses
assumptionVerify the hypothesis class is finite, the data are iid, and the loss is bounded before combining per-hypothesis concentration with a union bound.
Infinite classes, adaptive data, or unbounded losses require different capacity or concentration machinery.
- diagnostic
- question:logic-ml-foundations-030
Per-hypothesis tail becomes a uniform event
proof stepThe proof controls each fixed h with Hoeffding, unions the bad events across H, and solves the combined failure probability for epsilon.
Skipping the union step hides the exact origin of the log |H| sample-complexity penalty.
ERM consequence is not a deep-learning guarantee
boundaryThe result is a finite-class uniform-convergence theorem sufficient for ERM analysis, not a blanket explanation of modern overparameterized networks.
Overextending the theorem makes the site look like it is using classical bounds outside their assumptions.
- diagnostic
- question:logic-ml-foundations-030
Finite hypothesis class is doing real work
boundaryDo not apply this trail to an infinite or data-dependent class until the finite-class union step has been replaced by a capacity-control argument.
Treating the theorem as a generic generalization guarantee hides the exact point where finiteness is required.
- diagnostic
- question:logic-ml-foundations-030
Source Locators
Understanding Machine Learning (2014)
proofChapter 4 — Learning via uniform convergence
shalev-shwartz-ben-david-2014:ch4
- kind
- chapter
- review
- reviewed / A
- extract
- manual
Chapter-level support for the finite-class uniform convergence theorem and its Hoeffding plus union-bound proof pattern.
Understanding Machine Learning (2014)
proofCorollary 4.6 — Finite-class uniform convergence
shalev-shwartz-ben-david-2014:cor4.6
- kind
- corollary
- review
- reviewed / A
- extract
- manual
- number
- 4.6
Anchor: finite hypothesis class
Reviewed corollary-level support for finite-class uniform convergence.
Curated Trace
- 1Per-hypothesis tailinput bound
Each fixed h gets its own bounded-loss concentration inequality.
Checkpoint
Bounded loss in [0,1] is doing real work.
- 2Union over Hprobability step
The bad event is a union across hypotheses.
Checkpoint
The finite class assumption enters exactly here.
- 3Uniform convergencetheorem
Solving the combined failure probability gives the sqrt((log |H| + log 1/delta)/n) rate.
Checkpoint
Track both delta and |H|; neither is decoration.
- 4ERM guaranteedownstream
Uniform convergence controls the excess risk of empirical risk minimization.
Checkpoint
The theorem is sufficient for ERM, not a full account of modern deep learning.
Failure Modes
ERM consequence is not a deep-learning guarantee
The result is a finite-class uniform-convergence theorem sufficient for ERM analysis, not a blanket explanation of modern overparameterized networks.
Risk: Overextending the theorem makes the site look like it is using classical bounds outside their assumptions.
Check: The result is a finite-class uniform-convergence theorem sufficient for ERM analysis, not a blanket explanation of modern overparameterized networks.
- diagnostic
- question:logic-ml-foundations-030
Finite hypothesis class is doing real work
Do not apply this trail to an infinite or data-dependent class until the finite-class union step has been replaced by a capacity-control argument.
Risk: Treating the theorem as a generic generalization guarantee hides the exact point where finiteness is required.
Check: Do not apply this trail to an infinite or data-dependent class until the finite-class union step has been replaced by a capacity-control argument.
- diagnostic
- question:logic-ml-foundations-030