The Theorem That Says Nothing About Your Problem

Three binary inputs, so eight possible points, and a function assigns each one a label. There are $2^8 = 256$ such functions and that is all of them.

Show a learner four of the eight points, with their true labels, and score it on the other four. Do that for every one of the 256 functions and average:

The last row is a learner constructed to be wrong: it finds the nearest training point and predicts the opposite of its label. Averaged over all functions it is exactly as good as nearest neighbour, which is exactly as good as ignoring the data entirely.

This is the no free lunch theorem, and the table is not an approximation. Every entry is an exact enumeration of 256 functions.

A. Why it has to come out this way

For any four points held out, the 256 functions pair up. For each function $f$ there is another that agrees with $f$ on the four training points and disagrees on all four test points. A learner sees the same training data in both cases, so it makes the same predictions, so its errors on the pair sum to four out of four. Average over the pair: exactly one half.

Nothing about the learner enters that argument. It works for a deep network, for a lookup table, and for a random number generator.

B. And why it does not apply

The theorem averages over a uniform distribution on all functions. That is the assumption doing the work, and it is not a mild one: under it, the labels of the points you have not seen are independent of the labels of the points you have. A world drawn that way contains no learnable structure by construction, and the theorem says so.

Restrict the same average to the six functions that depend on a single bit - $f(x) = x_i$ or $f(x) = \neg x_i$, the simplest structure there is - and the same four learners give:

The ordering appears immediately, and it is the ordering anyone would predict: similarity-based prediction helps when similar inputs have similar labels, and the anti-learner is now precisely as bad as the learner is good.

Those two numbers belong to the split used throughout, in which the learner is shown the four points whose first bit is 0; averaged over all 70 ways of choosing the four training points, the six functions give 0.342857 for nearest neighbour and 0.657143 for the anti-learner, the same ordering.

Six of 256 is 2.3% of function space. Every real problem lives in a subset at least that special, and usually far more so.

C. What the theorem is actually for

It is not an argument that all methods are equal. It is a proof that no method is universally better, which has a precise and useful consequence: any learner's success on a class of problems is bought by matching that class, and paid for by failing on the complement.

That is the real content, and it is worth stating in the form it takes in practice:

• Every learner has an inductive bias, including the ones that do not advertise one. Nearest neighbours assume nearby inputs share labels; linear models assume additive effects; convolutional networks assume translation matters and locality helps. None of these is neutral and none can be.
• A benchmark result is a statement about a class of problems. "Method X beats method Y" is a claim about the distribution the benchmark was drawn from, not about learning in general.
• The useful question is never which algorithm is best. It is which assumptions your problem actually satisfies, and which method is built on those.

D. What it is not for

The theorem is regularly cited to end arguments it cannot settle: that model selection is futile, that domain knowledge cannot be encoded usefully, or that comparing methods is meaningless. All three are refuted by the second table. Under a structure as thin as "the label depends on one of three bits", one learner is twice as good as another, and it takes 256 exact evaluations to show it.