THE FOLD / RESPAWN / HARD RESET / THE NO FREE LUNCH
THE NO FREE LUNCH
a tie nobody can break
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Averaged over every possible objective function, all search algorithms perform identically. Not approximately — identically. Hill climbing, random search, your carefully tuned heuristic and a deliberately stupid one all have the same expected performance, because for every function where one wins there is another, equally admissible function where it loses by exactly as much. Wolpert and Macready proved it in 1997, and the result is quoted far more often than its hypothesis is.
LIT verified live: enumerating all 27 functions from a three-point domain to a three-value range, three different deterministic algorithms produce identical histograms of observed value-sequences, and identical means for best-found-so-far at every step — 1.0000, 1.4444, 1.6667 after one, two and three evaluations. Restricted to the 10 non-decreasing functions the tie collapses at once: the same three algorithms score 1.000, 1.500 and 1.200, a spread of 0.500.
LIT verified live: enumerating all 27 functions from a three-point domain to a three-value range, three different deterministic algorithms produce identical histograms of observed value-sequences, and identical means for best-found-so-far at every step — 1.0000, 1.4444, 1.6667 after one, two and three evaluations. Restricted to the 10 non-decreasing functions the tie collapses at once: the same three algorithms score 1.000, 1.500 and 1.200, a spread of 0.500.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at HARD RESET: whatever you learned about which algorithm is better, averaged over everything, resets to nothing.
AVAN (AI) built the second half deliberately, because the theorem is usually cited without it. “No algorithm is better than another” is false as normally understood; what is true is that no algorithm is better averaged over the set of all functions, and that set is dominated by functions of pure noise, which nobody has ever wanted to optimise. Restricting to the non-decreasing functions — a class so mild it barely deserves the name structure — is enough to separate the algorithms by half a unit. The theorem is not a warning that search is hopeless. It is a statement that every advantage is a bet on structure, and the bet is what the averaging removes.
AVAN (AI) built the second half deliberately, because the theorem is usually cited without it. “No algorithm is better than another” is false as normally understood; what is true is that no algorithm is better averaged over the set of all functions, and that set is dominated by functions of pure noise, which nobody has ever wanted to optimise. Restricting to the non-decreasing functions — a class so mild it barely deserves the name structure — is enough to separate the algorithms by half a unit. The theorem is not a warning that search is hopeless. It is a statement that every advantage is a bet on structure, and the bet is what the averaging removes.
3 ONE DIMENSION
Three algorithms, all 27 functions. The curves lie on top of each other.
4 TWO DIMENSIONS · INTERACTIVE
Restrict the function class and watch the tie break.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the space of all functions, and three paths through it that come out level.
AVAN’s addition (the inverse-companion): the forward reading is “no algorithm beats another on average.” The inverse is that the theorem is a measurement of the averaging set, not of the algorithms. It says the set of all functions has no structure to exploit — which is unsurprising, since a uniformly random function is exactly the object defined by having none. Read backwards, every working heuristic is a compressed claim about which functions are likely, and NFL is the observation that if you refuse to make such a claim you have refused to search. The theorem does not forbid a free lunch. It observes that you have declined to say where the restaurant is.
LIT enumerating all 27 functions from a three-point domain to a three-value range, three different deterministic algorithms produce identical histograms of observed value-sequences, and identical means for best-found-so-far at every step - 1.0000, 1.4444, 1.6667 after one, two and three evaluations; restricted to the 10 non-decreasing functions the tie collapses at once, the same three algorithms scoring 1.000, 1.500 and 1.200, a spread of 0.500
FIG The second half was built deliberately, because the theorem is usually cited without it. 'No algorithm is better than another' is FALSE as normally understood; what is true is that none is better averaged over the set of ALL functions, and that set is dominated by functions of pure noise, which nobody has ever wanted to optimise. Restricting to the non-decreasing functions - a class so mild it barely deserves the name structure - already separates them by half a unit. The theorem is not a warning that search is hopeless; it is a statement that every advantage is a bet on structure, and the bet is what the averaging removes.
FIG The second half was built deliberately, because the theorem is usually cited without it. 'No algorithm is better than another' is FALSE as normally understood; what is true is that none is better averaged over the set of ALL functions, and that set is dominated by functions of pure noise, which nobody has ever wanted to optimise. Restricting to the non-decreasing functions - a class so mild it barely deserves the name structure - already separates them by half a unit. The theorem is not a warning that search is hopeless; it is a statement that every advantage is a bet on structure, and the bet is what the averaging removes.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HARD RESET · David Lee Wise (ROOT0), with AVAN