# The no-free-lunch theorems of supervised learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 108 references that are in the map.
- First posted on arXiv 9 Feb 2022.

## Builds on (most cited first, 13 of 13)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Generalization in Deep Learning](https://mlsanity.com/paper/1710.05468/) (2017)
- [Inconsistency of Bayesian Inference for Misspecified Linear Models, and a Proposal for Repairing It](https://mlsanity.com/paper/1412.3730/) (2014)
- [On the marginal likelihood and cross-validation](https://mlsanity.com/paper/1905.08737/) (2019)
- [Minimum Description Length Revisited](https://mlsanity.com/paper/1908.08484/) (2019)
- [Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes](https://mlsanity.com/paper/1605.00252/) (2016)
- [Minimizers of the Empirical Risk and Risk Monotonicity](https://mlsanity.com/paper/1907.05476/) (2019)
- [What is important about the No Free Lunch theorems?](https://mlsanity.com/paper/2007.10928/) (2020)
- [Absolutely No Free Lunches!](https://mlsanity.com/paper/2005.04791/) (2020)

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

- [Scientific Inference With Interpretable Machine Learning: Analyzing Models to Learn About Real-World Phenomena](https://mlsanity.com/paper/2206.05487/) (2022)
- [The Benchmarking Epistemology: Validity Theory for Evaluating Machine Learning Models](https://mlsanity.com/paper/2510.23191/) (2025)
- [ML Interpretability: Simple Isn't Easy](https://mlsanity.com/paper/2211.13617/) (2022)
- [Statistical learning theory and Occam's razor: The core argument](https://mlsanity.com/paper/2312.13842/) (2023)
- [Relax, it doesn't matter how you get there: A new self-supervised approach for multi-timescale behavior analysis](https://mlsanity.com/paper/2303.08811/) (2023)
- [A General Theory for Compositional Generalization](https://mlsanity.com/paper/2405.11743/) (2024)
- [On the Computational Complexity of Ethics: Moral Tractability for Minds and Machines](https://mlsanity.com/paper/2302.04218/) (2023)
- [Solomonoff induction](https://mlsanity.com/paper/2603.20274/) (2026)
- [Transgressing the boundaries: towards a rigorous understanding of deep learning and its (non-)robustness](https://mlsanity.com/paper/2307.02454/) (2023)
- [Generating Skyline Datasets for Data Science Models](https://mlsanity.com/paper/2502.11262/) (2025)
- [When Is Inductive Inference Possible?](https://mlsanity.com/paper/2312.00170/) (2023)
- [The Knowledge-Behaviour Disconnect in LLM-based Chatbots](https://mlsanity.com/paper/2509.20004/) (2025)
- [How Complexity Contributes to Learning Opacity in Machine Learning](https://mlsanity.com/paper/2606.24953/) (2026)
- [Benign interpolation and Occam's razor](https://mlsanity.com/paper/2608.03386/) (2026)
- [Statistical learning theory and Occam's razor: Regularization](https://mlsanity.com/paper/2608.04049/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)

## Abstract (arXiv)

The no-free-lunch theorems promote a skeptical conclusion that all possible machine learning algorithms equally lack justification. But how could this leave room for a learning theory, that shows that some algorithms are better than others? Drawing parallels to the philosophy of induction, we point out that the no-free-lunch results presuppose a conception of learning algorithms as purely data-driven. On this conception, every algorithm must have an inherent inductive bias, that wants justification. We argue that many standard learning algorithms should rather be understood as model-dependent: in each application they also require for input a model, representing a bias. Generic algorithms themselves, they can be given a model-relative justification.