Generalization and Learning Guarantees

The No-Free-Lunch Theorem rules out a learner that succeeds on every learning task.

Programming

The Universal-Learner Question

A learning algorithm receives a training set and must predict labels for examples it has not observed. This creates a fundamental question: could one learner succeed on every possible learning task? The No-Free-Lunch Theorem answers no. For every learner, there is a task on which that learner fails.

Key point

The theorem rules out a learner that succeeds on every learning task. It does not say that every learner fails on every task.

Unobserved Labels

The proof uses a subset C of the domain X whose size is 2m, where m is the size of the training set. The learner observes only m instances from C, so half of the instances remain unobserved. The learner therefore has no information about the labels of those remaining instances. A target function can assign labels to them that contradict the learner's predictions.

After the learner sees labels for only half of the domain subset, what different label assignments could remain consistent with the observations?

Worked example

Half of the Domain Is Unseen

A learner receives m training instances from a subset C containing 2m instances. What information does the learner have about the other instances in C?

1
Count the instances
The subset C contains 2m instances, while the training set contains only m of them.
2
Identify the unseen portion
The remaining m instances in C were not observed by the learner.
3
Assess the labels
Because the learner has no information about the labels of those unobserved instances, a target function can assign labels that contradict the learner's predictions there.

Result

The learner cannot determine the labels of the unobserved instances from the training set alone.

Binary Classification and 0-1 Loss

In this setting, the No-Free-Lunch Theorem is applied to binary classification and evaluated with the 0-1 loss. A learner receives examples with binary labels, produces predictions for unobserved examples, and is evaluated according to the loss associated with those predictions. The source expresses successful prediction for the constructed target function as L_D(f) = 0.

How do an input, its true binary label, and a learner's prediction enter the 0-1 loss evaluation?

Empirical Risk Minimization

An ERM learner selects a hypothesis from its hypothesis class by minimizing the error measured on the training examples. The theorem's source example makes the hypothesis class especially simple: H = {f}. Since f is the only available hypothesis, an ERM learner using this class selects f.

How does an ERM learner compare its available hypotheses and choose the one with the lowest empirical error?

Worked example

A Learner That Succeeds on the Constructed Task

The hypothesis class is H = {f}, and the target function has L_D(f) = 0. What does an ERM learner using H select?

1
Inspect the hypothesis class
The class contains only one hypothesis: f.
2
Apply ERM selection
Because f is the only available hypothesis, the ERM learner selects f.
3
Evaluate the selected hypothesis
The source states that the target function has L_D(f) = 0, so this learner is successful for the task.

Result

The ERM learner succeeds on this task, even though the No-Free-Lunch Theorem guarantees that some other learner can be made to fail on a task.

Why No Learner Wins Everywhere

The theorem compares learners across possible tasks. For any particular learner, the proof constructs a task whose unobserved labels contradict that learner's predictions. This establishes that the learner cannot succeed on every task. However, another learner may succeed on that same task. Therefore, failure by one learner is not evidence that all learners must fail.

How can one learner fail on a task while another learner succeeds, and why does this rule out a universally best learner?

Learner Limitation Versus Task Impossibility

A learner's failure is a statement about the pairing of that learner with a task. It is not automatically a statement that the task itself cannot be learned. The source's ERM example demonstrates the distinction: an ERM learner with H = {f} succeeds on the constructed task because it selects f and the target function has L_D(f) = 0.

How should we distinguish a limitation of one learner from the stronger claim that no learner can succeed on the task?

Common mistake
Interpreting the theorem as saying that no learning task can be solved.
What it looks like
A learner fails on one task, so the task must be impossible.
Why it fails
The source gives an ERM learner that succeeds on the same constructed task.
Do this instead
Treat the result as a limitation of the particular learner, not proof that the task is impossible for every learner.
Common mistake
Treating the theorem as saying that every learner fails on the same task.
What it looks like
If one learner fails, all learners must fail there.
Why it fails
The theorem says that for every learner there is a task on which it fails; it does not say that all learners fail on one identical task.
Do this instead
Keep the learner and task pairing explicit.
Common mistake
Ignoring the unobserved part of the domain.
What it looks like
Assuming the learner knows the labels of all instances in C after seeing m of the 2m instances.
Why it fails
The remaining instances were not observed, so their labels are not supplied by the training set.
Do this instead
Separate observed instances from unobserved instances before judging the learner's predictions.
Common mistake
Forgetting the stated evaluation setting.
What it looks like
Applying this statement without noting the classification and loss assumptions.
Why it fails
The source frames the theorem here for binary classification with the 0-1 loss.
Do this instead
State the binary-classification and 0-1-loss setting when describing this formalization.

Check Your Understanding

MEDIUM

Suppose a learner observes m instances from a subset C containing 2m instances. Explain why the learner cannot be guaranteed to predict every remaining label correctly for every possible target function. Then explain why the failure of this learner does not prove that another learner must also fail.

Hints

Count how many instances remain unobserved.
Use the fact that the target function can contradict predictions on those unobserved instances.
Distinguish a statement about one learner from a statement about every possible learner.

Your attempt (not saved)

What do you think happens?

The hypothesis class is H = {f}, and the target function has L_D(f) = 0. What does an ERM learner using this hypothesis class select?

It selects f.
It has no available hypothesis.
It must select a hypothesis different from f.

Reveal answer

Answer:

It selects f.

f is the only hypothesis in H, so the ERM learner selects it. The source states that L_D(f) = 0, making this learner successful for the task.

Key Takeaways

1
The No-Free-Lunch Theorem rules out a single learner that succeeds on every possible learning task.
2
When a learner observes only m of 2m instances in a domain subset, the labels of the remaining instances are unobserved.
3
The theorem is considered here for binary classification under the 0-1 loss.
4
A target function can contradict a learner's predictions on unobserved instances.
5
One learner's failure does not prove that the task is impossible; another learner, such as the ERM learner using H = {f}, may succeed.

At a glance

No single learner is guaranteed to succeed on every possible learning task.
Unobserved labels leave room for a target function that contradicts a learner's predictions.
The result is formalized here for binary classification using the 0-1 loss.
Failure by one learner is not the same as impossibility of the task.
An ERM learner with H = {f} succeeds on the source's constructed task because it selects f and L_D(f) = 0.

Related concepts

More concepts starting with G