No Free Lunch Theorems for Optimization
David H. Wolpert, William G. Macready1997IEEE Transactions on Evolutionary Computation
Read it on doi.org(opens in a new tab)Why this one
Read this after No Free Lunch Theorems for Optimization? No, read it before you start believing any optimizer benchmark too much, then come back after Adam: A Method for Stochastic Optimization. Wolpert and Macready give you the cleanest version of a lesson engineers keep relearning: an algorithm wins only because the world you test it on has structure the algorithm exploits. People often misuse this paper as cynicism, as if it says search is hopeless or all methods are equal in practice. It says the opposite. Practical success comes from bias, priors, architecture, loss design, data shape, and constraints. If your optimizer, model, or heuristic works, ask what family of problems it assumes. That question will save you from cargo culting defaults, and it will make you better at choosing when to trust a method, when to tune it, and when to throw it away.
What to take away
- Averaged over all possible objective functions, every optimizer has the same performance.
- Any real advantage comes from matching an algorithm's bias to structure in the problem class.
- Benchmark wins mean little unless the tested tasks resemble the tasks you actually face.
Reads with
- Adam: A Method for Stochastic Optimization
a default optimizer only wins because deep learning workloads match its bias
- Understanding deep learning requires rethinking generalization
shows the same warning when capacity and test data replace optimizer benchmarks
- XGBoost: A Scalable Tree Boosting System
a case study in hand-built bias exploiting tabular data structure