An upper bound shows that an algorithm succeeds with enough examples. A lower bound asks a different question: can any algorithm succeed uniformly with fewer? The difficulty below is not slow computation. It is missing information: a label that has never been observed may still be either value.
A hard family on a shattered set
Let be a class of binary classifiers that shatters distinct points , with . Thus every binary labeling of these points is realized by at least one member of . Let be uniform on these points. A learner receives independent labeled examples from , labeled by an unknown fixed target in , and outputs a measurable binary classifier. The learner may be randomized and need not output a member of ; its private random bits are independent of the target and sample.
Write . For a randomized learner, both the sample and the learner's random bits contribute to the probability or expectation of its risk.
Theorem 2.3.1
(Unseen-point lower bound)
For every such learner, some fixed target satisfies
In particular, if , some fixed target has .
Proof
(Averaging over all labelings of the shattered set)
Temporarily choose the target labels independently and uniformly from , independently of the sample inputs and learner random bits. This random target is an averaging device: shattering ensures each labeling is realized by a target in the original class. Condition on the sampled points, their observed labels, and the learner's random bits. For each point absent from the sample, its target label remains a fair bit, independent of all that information. Whatever the learner predicts there, its conditional error probability is .
A particular point is absent with probability . Summing the conditional error over all points and averaging gives the displayed expectation. Since this is an average over finitely many realizable target labelings, at least one fixed target achieves at least that value; its choice is made before the actual sample for the resulting learning problem.
If , Bernoulli's inequality gives , so that target's expected risk is at least . Because ,
Rearranging proves the stated probability bound.
Proof X-ray
Where each hypothesis enters the averaging argument
The proof has one non-obvious move: replace the unknown target by a random one, condition on everything the learner can see, and observe that every unseen label is still a fair coin. Three hypotheses are used, each at one place.
Shattering is used only when passing from the random labeling back to the class. It guarantees that all labelings are realizable, so the average runs over genuine members of . Take instead. After one labeled example every label is known, there is nothing hidden, and the averaged error is .
Uniformity of and independence of the labels from the sample inputs are used at the conditioning step. Independence makes the label at an unseen point a fair bit given the learner's whole view, so no prediction there errs with probability below . Uniformity makes each point carry weight and be missed with the same probability ; for a non-uniform the same computation gives .
The argument closes because a mean of finitely many numbers is at most their maximum, so some fixed labeling has expected risk at least the mean. The chosen labeling depends on the learner and on , but not on the sample: the random target never exists in the learning problem itself. The Bernoulli step and the passage from expectation to probability are routine and use only .
This gives a necessary sample scale at least linear in for constant accuracy and confidence, even for an improper learner with unlimited computation. It does not say that every target is hard, or that the learner fails with probability one. Nor does it by itself prove the full dependence on arbitrary accuracy and confidence parameters.
Example. If and , the expected-risk lower bound is for some fixed target. These are four draws with replacement: repeated points reveal no new label, and the theorem accounts for that possibility.
Confidence can require rare examples
Now take two shattered points and fix . Let and . Choose two realizable targets that both label by zero but give opposite labels to . Let be the event that no training input equals ; then .
On , the joint distribution of the labeled sample and the learner’s independent random bits is the same under both targets, and has the same probability under each. For each possible output, its binary prediction at disagrees with at least one of the two targets. Under that target its risk is at least . Averaging over the two targets and learner randomness shows that one fixed target satisfies
Consequently, to guarantee failure probability at most for both targets, where , it is necessary that
The second inequality uses for and . All logarithms are natural. This is a necessary condition for this family, not a sufficient sample size for general PAC learning. The target and distribution are fixed for each learning problem; they are not allowed to change after seeing the sample.
Counterexample mode
Zero training error does not certify generalization
False claim: if a classifier has zero error on the training sample, then its true error is small. Take , the class of all labelings of , uniform , and target on . Suppose the sample is . The classifier agrees with both observed labels, so its training error is . But disagrees with at and , so . Another classifier, itself, is also consistent with this sample and has : the sample cannot tell and apart. Both draws land in with probability , and the lower bound guarantees expected risk at least for some target whatever the learner does. The claim is repaired only by a statement that controls the class: a consistent classifier is guaranteed small risk when is large compared with the capacity of , and by this theorem must be at least of order when shatters points.
What a lower bound does and does not say
The two constructions have different roles. The first counts how many independent label choices can be hidden on a shattered set. The second makes one informative point rare and explains the logarithmic dependence on a demanded failure probability. Neither uses a running-time assumption. An algorithm may have excellent performance on an easy distribution or a particular target without contradicting a worst-case lower bound.
The argument assumes independent examples and binary predictions. If a learner is allowed to query labels of chosen points, or the data distribution and target are restricted further, this proof does not automatically describe that different learning model. The selected hard target can depend on the learner, while the sample is still drawn only after the target is fixed.
Practice with solutions
Quick check
(For and , compute the expected-risk lower bound guaranteed for some target.)
Solution · Answer
.
Quick check
(For and , compute the rare-event lower bound on failure probability for one of the two targets.)
Solution · Answer
.
Quick check
(Why can a learner's internal randomization not remove the unseen-point argument?)
Solution · Answer
Condition on the learner's random bits as well as the observed sample; each unseen label is still an independent fair bit.
Quick check
(Does the first theorem say that every target has expected risk at least its displayed bound? Explain.)
Solution · Answer
No. Averaging proves the existence of at least one fixed hard target for that learner and sample size; other targets may be easy.