Symptom

Someone proposes replacing four hand-tuned models with one general-purpose learner, on the grounds that it is state of the art. Someone else objects: “No Free Lunch — no algorithm is better than any other, so you may as well keep what works.”

Both of these are wrong, and they are wrong about the same theorem. The first treats a learner as universally good; the second treats the theorem as saying comparison is meaningless. Meanwhile the actual result says something specific and useful, which is that whatever advantage your learner has comes from an assumption it makes about the world, and your job is to know what that assumption is and whether your problem satisfies it.

That reframing turns an unanswerable question — which algorithm is best — into an answerable one: which assumption does my data actually support.

Statement

Fix a finite input space $\mathcal{X}$ of size $N$ and binary labels. A target is any of the $2^N$ functions $\mathcal{X} \to {0,1}$. A learner sees a training set $S$ of $m$ labelled points and predicts on the rest.

No Free Lunch (Wolpert 1996). Let the target be drawn uniformly at random from all $2^N$ functions. Then for any two learners $A$ and $B$, the expected off-training-set error is equal:

$$\mathbb{E}_f\big[\mathrm{err}_{\text{off}}(A, f)\big] = \mathbb{E}_f\big[\mathrm{err}_{\text{off}}(B, f)\big] = \tfrac{1}{2}.$$

Averaged over all problems, every learner ties, including the one that predicts the opposite of what the data suggests, and including the one that ignores the data entirely.

The learning-theory form (Shalev-Shwartz and Ben-David, Thm 5.1). For any learner and any training size $m \le |\mathcal{X}|/2$, there exists a distribution on which the learner has error $\ge 1/8$ with probability $\ge 1/7$, while some hypothesis achieves zero error. There is no universal learner.

The two forms say different things. The first is about averaging over a measure; the second is a genuine worst-case existence claim, and it is the one that makes finite VC dimension necessary in the fundamental theorem.

Argument

The counting argument, which is the entire content. Let $U = \mathcal{X} \setminus S$ be the $N - m$ unseen points. A target consistent with the observed labels can extend to $U$ in any of $2^{N-m}$ ways, and under the uniform measure every one is equally likely.

Take any single unseen $x \in U$. Among the consistent targets, exactly half label it 0 and half label it 1 — because the extensions come in pairs identical everywhere except at $x$. So whatever the learner predicts at $x$, it is right for exactly half the consistent targets. Averaged over targets, error at $x$ is $1/2$; averaged over $U$, the off-training-set error is $1/2$. This holds for every learner, because the argument never mentioned the learner. $\blacksquare$

Why this is T004 pointed at learners. The no-universal-compressor argument is the same pigeonhole in different clothes: a bijection from $n$-bit strings to codewords must lengthen as many strings as it shortens, so the total gain summed over all inputs is zero. Here, the total accuracy summed over all targets is fixed, so an algorithm that does better on one set of targets does exactly as much worse on the complement. Compression and prediction are the same operation — both bet that some inputs are more likely than others — and both obey the same conservation law when you refuse to let them bet.

Now the sleight of hand, which is in the word “all”. The uniform measure over all $2^N$ functions is not a neutral choice. It is an extremely strong and extremely specific assumption, and what it assumes is that the label at one point tells you nothing about the label at any other point. A function drawn uniformly is white noise on $\mathcal{X}$. There is no structure to find, so of course no method finds any.

Put a number on how far this is from any real task. With $N = 2^{100}$ possible inputs, there are $2^{2^{100}}$ targets. The ones with any description shorter than the function itself — every function that is smooth, or sparse, or computable in reasonable time, or generated by a physical process — are a vanishing fraction of that set. Real tasks are drawn from that vanishing fraction, essentially by definition of being a task someone cares about. The uniform average is dominated by functions no one will ever ask about.

So what is the useful reading? That performance is a relationship between an algorithm and a distribution over problems, and the algorithm’s implicit bias is what names that distribution:

  • $k$-nearest neighbours assumes nearby points share labels. Excellent when the metric is meaningful, useless in high dimensions with an arbitrary metric.
  • Linear models assume the decision boundary is a half-space, which is why they do so well on wide sparse text features and so badly on XOR.
  • Convolutional networks assume translation equivariance and locality. That assumption is worth more on images than any amount of parameter tuning, and worth nothing on tabular data with permuted columns.
  • Gradient-boosted trees assume the target is a sum of axis-aligned piecewise constants, which is why they still beat neural networks on heterogeneous tabular data.

Back to the argument at the top. The right question is not “is the general learner better” but “does the general learner’s inductive bias match all four of the problems the hand-tuned models cover.” If those problems are images and text, plausibly yes. If one of them is a tabular fraud model with 300 heterogeneous features, the tree is not losing on merit and should stay.

Forbids

A learner that outperforms all others across all problem distributions. Not undiscovered — impossible. Any claim of universal superiority is either scoped to a class of problems or wrong.

Learning without inductive bias. A method that makes no assumption predicts nothing off its training set. “Let the data speak for itself” describes no algorithm.

Benchmark results as evidence of universal quality. A benchmark is a sample from a distribution over problems. Results transfer only insofar as your problem resembles that distribution, and this is why leaderboard rank so often fails to survive contact with a production dataset.

Meta-learning your way out. A learner that selects among learners is itself a learner and is covered by the theorem. Its bias is now over algorithm-problem pairs, and it is still a bias.

Does not forbid

It does not say all algorithms perform equally on your problem, which is the misreading and the reason the slogan is worse than useless in practice. The average is over a measure your problem is not drawn from. On any specific distribution the differences are enormous and entirely real, and measuring them is exactly what you should be doing.

It does not say comparison is meaningless. It says comparison must be scoped. “Better on natural images” is a coherent, testable, valuable claim. “Better” full stop is not.

It does not forbid a learner that dominates on all problems humans care about. The set of humanly-interesting functions is tiny and structured, and nothing in the theorem prevents one method from covering it. Whether such a method exists is an open empirical question, and current large models are the most serious attempt at one.

It does not apply to the same-distribution setting people usually work in. Once you fix a distribution and ask for a hypothesis with low error on that distribution, the fundamental theorem of T096 applies and gives positive results. NFL is about the choice of the distribution.

It does not make model selection futile. It makes model selection the whole job. Choosing an architecture, a kernel, a feature representation, or a prior is choosing which class of problems you will be good at, and this is the theorem’s actual advice.

Boundary

  • Off-training-set error is essential to the statement. Wolpert measures error only on unseen points; including training points breaks the symmetry and the equality no longer holds exactly.
  • The uniform measure is doing all the work. Under any non-uniform prior — such as one favouring low-complexity functions — the equality fails and some learners really are better a priori. This is the standard and correct rebuttal.
  • The finite-$\mathcal{X}$ version is the clean one. Continuous input spaces need more care, and the results are less crisp than the slogan implies.
  • It concerns predictive accuracy only. Nothing is said about training cost, interpretability, latency, or robustness, which are frequently what actually decides the choice.
  • The optimisation analogue is separate. Wolpert and Macready’s NFL for search has its own statement and its own hypothesis of closure under permutation, which real fitness landscapes also fail. Conflating the two is common.

The sentence to keep: every learner is a bet on what the world looks like, and the theorem says only that you cannot decline to bet. Knowing which bet you have placed is the practical skill.