# What is important about the No Free Lunch theorems?

arXiv: https://arxiv.org/abs/2007.10928 · HTML: https://mlsanity.com/paper/2007.10928/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2020.

## Built on by (most cited first, 9 of 9)

- [The no-free-lunch theorems of supervised learning](https://mlsanity.com/paper/2202.04513/) (2022)
- [Impossibility Results in AI: A Survey](https://mlsanity.com/paper/2109.00484/) (2021)
- [Quantifying Relevance in Learning and Inference](https://mlsanity.com/paper/2202.00339/) (2022)
- [A General Theory for Compositional Generalization](https://mlsanity.com/paper/2405.11743/) (2024)
- [Know the Ropes: A Heuristic Strategy for LLM-based Multi-Agent System Design](https://mlsanity.com/paper/2505.16979/) (2025)
- [Quantifying Human Priors over Social and Navigation Networks](https://mlsanity.com/paper/2402.18651/) (2024)
- [A Link between Coding Theory and Cross-Validation with Applications](https://mlsanity.com/paper/2103.11856/) (2021)
- [What can we know about that which we cannot even imagine?](https://mlsanity.com/paper/2208.03886/) (2022)
- [Empirical Evaluation of No Free Lunch Violations in Permutation-Based Optimization](https://mlsanity.com/paper/2603.03613/) (2026)

## Abstract (arXiv)

The No Free Lunch theorems prove that under a uniform distribution over induction problems (search problems or learning problems), all induction algorithms perform equally. As I discuss in this chapter, the importance of the theorems arises by using them to analyze scenarios involving {non-uniform} distributions, and to compare different algorithms, without any assumption about the distribution over problems at all. In particular, the theorems prove that {anti}-cross-validation (choosing among a set of candidate algorithms based on which has {worst} out-of-sample behavior) performs as well as cross-validation, unless one makes an assumption -- which has never been formalized -- about how the distribution over induction problems, on the one hand, is related to the set of algorithms one is choosing among using (anti-)cross validation, on the other. In addition, they establish strong caveats concerning the significance of the many results in the literature which establish the strength of a particular algorithm without assuming a particular distribution. They also motivate a ``dictionary'' between supervised learning and improve blackbox optimization, which allows one to ``translate'' techniques from supervised learning into the domain of blackbox optimization, thereby strengthening blackbox optimization algorithms. In addition to these topics, I also briefly discuss their implications for philosophy of science.