No-Free-Lunch Theorem
Shattering means realizing every possible 0/1 labeling on a chosen set.
The Universal Learner Challenge
Imagine a learner that receives some labeled examples and must predict labels for examples it has not observed. The central question is whether one learning algorithm can succeed on every possible learning task. The No-Free-Lunch Theorem says no: for every learner, there is a task on which that learner fails. This does not mean that every learner fails on the same task, or that the task itself cannot be learned. It means that no single learner succeeds universally without useful restrictions on the tasks or hypotheses it considers.
A limitation of one learning algorithm is not a proof that learning the task is impossible. Another learner may succeed on the very same task.
Shattering Every Labeling
To study the capacity of a hypothesis class H, choose a finite set C from the input space X. Every point in C can receive label 0 or label 1. The class H shatters C when it can realize every possible 0/1 labeling of the points in C. The important test is therefore not whether H can produce one particular labeling. The test is whether H can produce all possible labelings on that chosen set.
Testing Whether Three Points Are Shattered
A chosen set C contains three points. Determine what must be checked before saying that a hypothesis class shatters C.
List the possible labelings: Each of the three points can receive label 0 or 1, so the test considers every possible 0/1 labeling of the set.
Check the hypothesis class: For each labeling, ask whether some hypothesis in H realizes that labeling on C.
Require all labelings: The set C is shattered only if H realizes every possible labeling, not merely one or several of them.
A successful realization of every labeling proves that this particular three-point set is shattered.
From Shattered Sets to VC-Dimension
The VC-dimension of H, written VCdim(H), is the maximal size of a set shattered by H. It records the largest number of points on which the hypothesis class can realize every binary labeling.
| Object | What it tells you |
|---|---|
| A shattered set C | This particular set can receive every possible 0/1 labeling from hypotheses in H. |
| A shattered set of size three | VCdim(H) is at least three, unless the class cannot shatter that set. |
| VCdim(H) | The maximum size of any set that H can shatter. |
| Infinite VC-dimension | H can shatter sets of arbitrarily large finite size. |
Capacity and PAC Learnability
The connection with learning appears in the PAC framework. When PAC learnability is studied for H, the adversary is restricted to distributions for which some hypothesis in H achieves zero risk. If a distribution is concentrated on a set C, then the behavior of H on C becomes central. The class's ability to realize labelings on C describes how much freedom it has in that situation. VC-dimension summarizes this capacity through the largest set on which every binary labeling can be realized.
VC-dimension measures expressive capacity. PAC learning asks whether that capacity can support learning from finite samples under the stated distributional conditions.
Why Unseen Labels Stay Uncertain
The theorem's proof uses a subset C of the domain X with size 2m, where m is the training-set size. The learner observes only m instances from C, leaving the remaining instances unobserved. Since the learner has no information about the labels of those unobserved instances, a target function can be chosen whose labels contradict the learner's predictions there.
What do you think happens?
If a learner has observed only half of the instances in C, what determines the labels on the remaining instances?
Reveal answer
Answer: The learner has no information about those unobserved labels from the training observations alone.
The proof exploits this absence of information by choosing a target function whose labels contradict the learner's predictions on unobserved instances.
The 0-1 Loss Formalization
In this setting, the theorem concerns binary classification measured with the 0-1 loss. A prediction contributes an error when it disagrees with the target label, and the learner's performance is expressed through its loss on the distribution. The theorem's construction makes the learner wrong on unobserved instances by selecting a target function whose labels contradict the learner's predictions there.
Different Learners, Same Task
The phrase for every learner is essential. The theorem says that each particular learner has some task on which it fails. It does not say that all learners fail on that task. The source gives a direct contrast: let the hypothesis class be H = {f}. An ERM learner using this class has only one available hypothesis, f, so it selects f. If the target function has L_D(f) = 0, this ERM learner succeeds on that task.
When interpreting a failure, name the learner and the task separately. Say that a particular learner fails on a constructed task, not that the task is unlearnable by every possible learner.
Common Interpretation Errors
Treating one shattered set as the VC-dimension
That observation proves only that the VC-dimension is at least three. Larger shattered sets may still exist.
Fix:
To establish equality, rule out every larger shattered set.Checking only one labeling
Shattering requires realizing every possible 0/1 labeling on C.
Fix:
Check all possible labelings and require a hypothesis for each one.Reading the theorem as saying every learner fails on every task
The theorem says that for every learner there is a task on which it fails. It does not deny success on other tasks.
Fix:
Keep the quantifiers separate: a learner can succeed on some tasks and fail on another.Concluding that a failed learner proves the task is impossible
Another learner may succeed on the same task.
Fix:
Compare learners before making a claim about learnability of the task itself.
Check Your Understanding
A hypothesis class shatters a set C of three points. What can you conclude immediately, and what additional fact would be needed to determine the exact VC-dimension?
Hints
- Separate the claim about this particular set from the claim about the largest shattered set.
- Ask whether larger sets have been ruled out.
A learner observes m instances from a domain subset C of size 2m. Explain why the unobserved instances are central to the No-Free-Lunch construction.
Hints
- Count how many instances remain unobserved.
- Relate missing labels to the learner's predictions and 0-1 errors.
Explain why an ERM learner over H = {f} can succeed on a task even though the No-Free-Lunch Theorem rules out a universal learner.
Hints
- The class contains only one available hypothesis.
- Use the condition L_D(f) = 0.
Key Takeaways
- A hypothesis class shatters a set when it realizes every possible 0/1 labeling on that set.
- VCdim(H) is the maximum size of a set shattered by H; one shattered three-point set proves only that the VC-dimension is at least three.
- VC-dimension summarizes hypothesis-class capacity and is relevant to PAC learnability.
- The No-Free-Lunch Theorem says that no single learner succeeds on every possible learning task.
- Unobserved labels allow a target function to contradict a learner's predictions, while another learner may still succeed on the same task.
Key Takeaways
- Shattering means realizing every possible binary labeling on a chosen set.
- The VC-dimension is the largest size of any set that the hypothesis class can shatter.
- The No-Free-Lunch Theorem rules out a universally successful learner for all learning tasks.
- Its construction uses unobserved instances whose labels can contradict a learner's predictions under binary 0-1 loss.
- A learner's failure on one task does not imply that another learner cannot succeed on that task.