A finite-class uniform-convergence bound
Research context
postgraduate concept · established · As of 2026-10-10
For a finite hypothesis class H, iid observations and losses in [0,1], Hoeffding plus a union bound gives probability at most 2|H|exp(−2n epsilon²) that any empirical risk differs from its population risk by more than epsilon.
Key knowledge
For a finite hypothesis class H, iid observations and losses in [0,1], Hoeffding plus a union bound gives probability at most 2|H|exp(−2n epsilon²) that any empirical risk differs from its population risk by more than epsilon. The bound supports selecting a predictor after seeing the sample because it is simultaneous over the fixed class. A class chosen adaptively on the same sample needs additional reasoning.
Values and equations
Pr[sup_(h in H)|R_S(h)−R_D(h)|>epsilon] ≤ 2|H| exp(−2n epsilon²)
- H
- Fixed finite predictor class
- n
- Number of iid observations
- epsilon
- Allowed risk error
- R_S,R_D
- Empirical and population risks
Conditions and scope
- H is a fixed finite class; loss is bounded in [0,1], and samples are iid from the target law.
- The bound is sufficient and often conservative; unbounded squared loss needs tail/moment assumptions or another bound.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: Chapters 2–6 PAC/VC, 11 validation, 13 regularization, 14 stochastic gradient and 23 PCA. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-finite-class-uniform-bound
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference