Core ML

No Free Lunch

Averaged across every possible problem, no learning algorithm beats another — an edge on the problems you care about costs ground somewhere else.

Averaged across every possible target function, two very different algorithms land on the exact same accuracy — one algorithm's advantage on some problems is always paid for by a matching disadvantage on others

Why Does This Exist?

Someone new to the field, comparing a handful of benchmark leaderboards, reasonably asks: which algorithm is just better? Gradient boosting keeps winning tabular competitions. Surely that settles it, and everyone should default to gradient boosting everywhere.

It doesn't settle it, and the reason is more precise than "it depends." The No Free Lunch theorem states something specific and provable: averaged across every possible problem a learning algorithm could face, every algorithm achieves exactly the same performance. Gradient boosting's edge on tabular competition data isn't a universal property of the algorithm — it's a property of the match between gradient boosting's assumptions and the specific structure that real tabular data tends to have. Change the structure enough, and the edge evaporates or reverses.

Think of It Like This

A key that opens every door opens none particularly well

A locksmith could design one master key shaped to have a decent chance of opening any lock, or a set of keys each precisely cut for one specific lock. Averaged over every lock that exists, the master key's overall "opens it well" score and the sum of every precisely-cut key's score come out identical — because a shape compromise that helps with some locks necessarily hurts with others.

A precisely-cut key that opens your front door perfectly is not evidence that it's a better key in some universal sense. It's evidence that its specific shape happens to match your specific lock. No Free Lunch is the same statement about learning algorithms and problems: a good match to the problem you actually have, not a universally superior algorithm.

How It Actually Works

What the theorem actually claims

Formally: averaged uniformly over every possible target function an algorithm could be asked to learn, every learning algorithm's expected performance on unseen data is identical — including comparing a sophisticated method against one that ignores the input entirely and predicts randomly. This holds specifically when every possible function is weighted equally, with no assumption about which functions are more likely to occur in the real world.

Why real-world results don't contradict it

Real datasets are never drawn from "every possible function, uniformly." Images have spatial structure — nearby pixels correlate strongly. Language has syntactic and semantic structure. Tabular business data usually has some genuinely relevant features mixed with noise, not an adversarially scrambled arrangement. Every practical learning algorithm bakes in an assumption — an inductive bias — about what kind of structure it expects to find, and it performs well exactly to the degree that assumption matches the real structure of real problems. Convolutional networks assume spatial locality matters; that assumption is almost always right for photographs and almost never checked because it's so reliably true. No Free Lunch is what's being traded away to get that reliability: performance on the vast space of problems where spatial locality is irrelevant or actively misleading.

The practical consequence: match the algorithm to the problem's structure

No Free Lunch doesn't say all algorithms perform equally on any specific dataset — that would contradict decades of empirical benchmarking. It says there's no algorithm that's the right match for every dataset's structure simultaneously. The actual work of applied machine learning is understanding what structure a specific problem likely has — smoothness, sparsity, hierarchy, locality — and choosing (or designing) an algorithm whose inductive bias matches it, rather than searching for one universally correct default.

Show Me the Code

Two very different algorithms, averaged over every possible target function on a small input space, landing on identical accuracy.

1import numpy as np2
3
4def eval_over_all_functions(n_bits: int, n_train: int) -> tuple[float, float]:5    """Every function from {0,1}^n_bits to {0,1} is a possible target.6    Compare 'always predict 0' against 'predict the training-set majority label'."""7    train_idx = np.arange(n_train)8    test_idx = np.arange(n_train, 2 ** n_bits)9    acc_zero, acc_majority = 0.0, 0.010    for f in range(2 ** (2 ** n_bits)):11        labels = np.array([int(b) for b in format(f, f'0{2**n_bits}b')])12        train_y, test_y = labels[train_idx], labels[test_idx]13        pred_zero = np.zeros(len(test_idx), dtype=int)14        majority = 1 if train_y.mean() > 0.5 else 015        pred_majority = np.full(len(test_idx), majority)16        acc_zero += (pred_zero == test_y).mean()17        acc_majority += (pred_majority == test_y).mean()18    n_functions = 2 ** (2 ** n_bits)19    return acc_zero / n_functions, acc_majority / n_functions20
21
22zero_acc, majority_acc = eval_over_all_functions(n_bits=3, n_train=4)23print(f"'always predict 0':        average accuracy = {zero_acc:.4f}")24print(f"'predict training majority': average accuracy = {majority_acc:.4f}")25# -> 'always predict 0':        average accuracy = 0.500026# -> 'predict training majority': average accuracy = 0.5000

Both algorithms average exactly 0.5000 across all 256 possible target functions over this small input space — not approximately equal, exactly equal. "Predict the training majority" looks obviously smarter than "always predict 0," and it is, on the functions where the majority label is actually informative. Averaged over every function, including the ones deliberately constructed to make majority-voting wrong, that advantage is paid back in full.

Watch Out For

Treating a leaderboard win as proof of a universally better algorithm

An algorithm winning a specific competition tells you it matched that competition's data structure well — not that it's the correct default for the next problem, especially one with different structure (different feature types, different noise characteristics, different scale). Ask what structural assumption the winning algorithm makes and whether the new problem actually shares that structure, rather than defaulting to the last leaderboard's winner.

Concluding that algorithm choice therefore doesn't matter

No Free Lunch is sometimes misquoted as "all algorithms are equally good in practice," which is the opposite of the useful lesson. Real problems are never uniform draws over all possible functions, so matching an algorithm's inductive bias to a problem's actual structure produces large, real, and entirely legitimate performance differences. The theorem explains why that matching matters — it doesn't say matching is pointless.

The Quick Version

Averaged over every possible target function with no assumption about real-world structure, every learning algorithm performs identically.
Real problems have structure — spatial, sequential, sparse, hierarchical — and algorithms perform well by encoding an inductive bias that matches that structure.
A benchmark win reflects a good match between an algorithm's assumptions and that benchmark's data, not universal superiority.
The practical lesson is to understand a problem's likely structure and choose an algorithm accordingly, rather than searching for one default that wins everywhere.