Finite Hypothesis Classes
A hypothesis is in HB when its risk is beyond the permitted accuracy level.
Try it: Empirical Risk Minimization
How ERM picks the hypothesis in a finite class H with the smallest empirical risk on a random sample , how far its true risk can be from , 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 can be computed exactly.
- Draw : 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 , and compute its true risk from . For the class of all functions, ERM simply memorises S: the majority label at each seen point, 0 elsewhere.
- ERM returns , the first hypothesis with the smallest . Compare with , and split into plus .
- Repeat with R fresh samples and count how often . The finite-class bound says (realizable, ) or (agnostic, ) keeps that frequency at most δ.
- Run the same samples through richer and richer classes: falls, the average rises, and memorising (all functions) reaches small with a large .
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 ~ Dm 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 LS 0.0617). Lowest average LD(hS): 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 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…
The Learning Guarantee
A learning algorithm does not receive the distribution D directly. It receives a training set sampled from that distribution and must choose a hypothesis. Finite hypothesis classes give us a reassuring result: every finite collection of possible hypotheses is PAC learnable. The important question is how that conclusion is assembled from sampling, risk thresholds, probability bounds, and sample complexity.
The finite-class result establishes learnability, but the supplied result does not provide a numerical sample bound or a formula for calculating the exact number of required examples.
Building the Training Set
The notation S ∼ Dm describes a random training set S containing m examples. The i.i.d. assumption says two things about how those examples are obtained: they are independent of one another, and they are all drawn from the same distribution D. Thus, the training set is a sample of m independent draws from one common source distribution.
Reading S ∼ Dm
Interpret the statement S ∼ Dm.
- 1Identify S
S is the random training set.
- 2Identify m
m is the number of examples in that training set.
- 3Identify Dm
The notation indicates that the m examples are independently drawn from the same distribution D.
S is a training set of m independent examples, all sampled from D.
Risk and the Accuracy Threshold
An ERM learner receives a training set rather than direct access to D. Its output depends on the sampled set S, so the analysis must connect what happened on S with what may happen under D. The notation L(D,f)(hS) refers to the risk of the hypothesis hS produced from the training set. The parameter ϵ sets the boundary for acceptable risk: a hypothesis whose risk is greater than ϵ is beyond the permitted accuracy level.
Classifying an Output
Suppose the permitted risk threshold is ϵ. How should two possible learner outputs be interpreted?
- 1Output A
If L(D,f)(hS) is at most ϵ, the output meets the accuracy boundary being studied.
- 2Output B
If L(D,f)(hS) is greater than ϵ, the output belongs to the unacceptable-risk case for this guarantee.
The threshold separates approximate correctness from learner failure; it does not separate perfection from imperfection.
Collecting Bad Events
To analyze failure, define the set HB of bad hypotheses. A hypothesis is in HB when its risk is beyond the permitted accuracy level. Instead of examining every possible training-set outcome separately, the analysis associates failure events with these bad hypotheses and then combines those events.
The Union Bound says that the probability of a union of events is no greater than the sum of the probabilities of the individual events. In a finite-class analysis, each bad hypothesis contributes an event, and the Union Bound turns the separate probability bounds into one overall bound on failure. The events do not need to be disjoint. If they overlap, adding their probabilities may overcount some outcomes, which is why the sum is an upper bound rather than necessarily the exact probability.
Applying the Union Bound
Suppose failure can occur through bad-hypothesis events A or B. What can be said about the probability of overall failure?
- 1Name the combined event
Overall failure is the event that A or B occurs.
- 2Add the separate bounds
The Union Bound uses the probability bound for A plus the probability bound for B.
- 3Account for overlap
A and B may happen together, so the sum is an upper bound and need not equal the exact probability.
The probability of A or B is at most the sum of the probabilities of A and B.
Why Finiteness Is Sufficient
A finite hypothesis class contains a finite collection of possible hypotheses. When the bad hypotheses are considered, there are only finitely many associated bad-hypothesis events to combine. The Union Bound can therefore collect their individual probability bounds into one overall failure bound. This is the mechanism behind the result that every finite hypothesis class is PAC learnable with sample complexity.
Sample Complexity in Context
Sample complexity is the number of samples required for learning a hypothesis class. In a PAC learnability guarantee, the required sample size is connected to the accuracy threshold ϵ, the probability of failure, and the hypothesis class being learned. The supplied finite-class statement establishes that such a sample complexity exists for every finite hypothesis class, but it does not provide a numerical formula.
| Question | What the finite-class result says | What it does not say |
|---|---|---|
| Is learning possible? | Every finite hypothesis class is PAC learnable. | It does not give a numerical sample bound. |
| What is sample complexity? | It is the number of samples required for learning. | The result does not calculate the exact number here. |
| What role does finiteness play? | It makes the finite-class result sufficient for learnability. | Finiteness is not the complete characterization of learnability. |
Scope of the supplied finite-class result
Beyond Counting Hypotheses
Finiteness is sufficient in the result presented here, but it is not the deepest characterization of learnability. Some infinite hypothesis classes are learnable too. The broader measure introduced for this purpose is VC dimension, described as a combinatorial measure that determines the PAC learnability of a class. This shifts attention from simply counting hypotheses to examining structural properties of the class.
Common Reasoning Mistakes
Common mistake Treating S ∼ Dm as m identical examples.
What it looks likeReading the notation as if the training set repeats one fixed example m times.
Why it failsThe examples are independent draws from the same distribution D; same distribution does not mean identical outcomes.
Do this insteadInterpret S as a random set of m independent examples sampled from D.
Common mistake Calling every output with nonzero risk a failure.
What it looks likeAssuming that only a perfect hypothesis can satisfy the learning guarantee.
Why it failsThe parameter ϵ defines the permitted risk boundary. The relevant failure case is L(D,f)(hS) greater than ϵ.
Do this insteadCompare the output risk with ϵ rather than with zero.
Common mistake Assuming the Union Bound requires disjoint events.
What it looks likeRefusing to combine bad-hypothesis events because two of them might occur together.
Why it failsThe Union Bound still applies when events overlap; overlap is why the sum is an upper bound rather than necessarily the exact probability.
Do this insteadAdd the separate probability bounds to obtain an upper bound on their union.
Common mistake Claiming that the finite-class result supplies an exact sample count.
What it looks likeReporting a numerical value for sample complexity without a supplied bound or formula.
Why it failsThe result establishes learnability and the existence of sample complexity, but the supplied statement does not provide a numerical sample formula.
Do this insteadState the qualitative conclusion and avoid inventing an exact number.
Common mistake Concluding that every infinite class is unlearnable.
What it looks likeTreating finiteness as a necessary condition for PAC learnability.
Why it failsThe source notes that some infinite classes are learnable.
Do this insteadRecognize finiteness as sufficient for the presented result, while VC dimension gives a broader perspective.
Check Your Understanding
A learner receives S ∼ Dm and outputs hS. Explain what must be true about the sampling process, what comparison determines whether the output crosses the accuracy boundary, and how the Union Bound helps when several bad hypotheses are possible.
Hints
- Mention independence and the common distribution D.
- Use the comparison between L(D,f)(hS) and ϵ.
- Describe the Union Bound as combining separate event-probability bounds.
A class is finite, but no numerical sample bound is provided. What conclusion is justified, and what conclusion is not justified?
Hints
- Use the finite-class PAC learnability result.
- Separate existence of sample complexity from an exact numerical formula.
Key Takeaways
- S ∼ Dm means that the training set contains m independent examples drawn from the same distribution D.
- The accuracy parameter ϵ is a risk threshold: the output is in the unacceptable-risk case when L(D,f)(hS) is greater than ϵ.
- The Union Bound combines probability bounds for separate bad-hypothesis events into an upper bound on their union, even when those events overlap.
- Every finite hypothesis class is PAC learnable with sample complexity, but the supplied result does not give an exact numerical sample formula.
- Finiteness is sufficient for the presented result, while VC dimension provides a broader combinatorial perspective because some infinite classes are also learnable.