Lost in Latent Space

No Free Lunch is doing a lot of work it wasn’t designed for

The NFL theorem (Wolpert 1996, Wolpert & Macready 1997 for optimization) gets trotted out in arguments roughly weekly on this site, and it is almost always doing more rhetorical work than it can support. Worth pinning down what it actually says.

Strong form: averaged over all possible target functions $f: X \to Y$, every learning algorithm has the same expected off-training-set error. Pick your favorite — kNN, gradient boosting, a 70B transformer, literally return random.choice(Y) — they all tie if you weight every function on $X$ equally.

That’s the whole theorem. The trick is “averaged over all possible target functions.” There are $

Y

^{

X

}$ of those, and the overwhelming majority are pure noise — functions where input $x$ and input $x’$ that differ in one bit produce wildly different outputs with no structure relating them. Uniform measure over that space is uniform measure over a sea of essentially-random mappings.

The real world is not drawn uniformly from that space. Images of cats have local correlations. Language has long-range syntax. Protein folding obeys physics. Etc. So the theorem’s premise — uniform prior over all functions — is the part that’s wrong about reality, not the conclusion.

What NFL does establish, cleanly:

1. You cannot get prior-free generalization. Every learning algorithm encodes an inductive bias, and that bias is what does the work. “Model-free” / “assumption-free” rhetoric is marketing.
2. Universal superiority is impossible. No algorithm dominates every other on every problem. The “best” algorithm is a function of the problem distribution, full stop.
3. Benchmark wins don’t transfer for free. A method that crushes ImageNet has no theorem-level guarantee about CIFAR-N, let alone tabular data.

What it does not establish, despite popular usage:

• It does not say “deep learning is no better than random forests” — that would require a uniform prior over real-world problems, which nobody has any reason to believe.
• It does not justify “well, any model could work, so we’ll just pick the simplest one.” Simplicity is itself an inductive bias; you’ve made a strong claim, you just haven’t labeled it.
• It does not mean comparing algorithms is meaningless. It means comparing them without specifying the problem class is meaningless.

Adjacent theorems people conflate it with:

• Schaffer’s conservation law (1994) — similar flavor, predates Wolpert, narrower setup. Sometimes the version people actually want.
• Hume’s problem of induction — NFL is basically a measure-theoretic restatement of it, two and a half centuries later. The philosophers got there first.

The honest takeaway: NFL is a constraint on rhetoric, not on engineering. If you’re claiming an algorithm is universally good, NFL rules you out. If you’re claiming an algorithm works well on a specified distribution because of a specified inductive bias, NFL has nothing to say to you. Most production ML is the second thing pretending to be the first to sound humble.

What’s next

The natural sequel is the “no free lunch for cross-validation” variant (Wolpert again, 2001) which closes the obvious escape hatch — you can’t even use CV to dodge it, because the meta-procedure inherits the same prior dependence. Worth reading alongside Sterkenburg & Grünwald (2021), who argue NFL is much less of a constraint once you condition on the realistic problem set, not the uniform one.