No free lunch theorem

This article is about mathematical folklore. For treatment of the mathematics, see No free lunch in search and optimization.

In mathematical folklore, the "no free lunch" (NFL) theorem (sometimes pluralized) of David Wolpert and William Macready, alludes to the saying "no such thing as a free lunch", that is, there are no easy shortcuts to success. It appeared in the 1997 "No Free Lunch Theorems for Optimization".[1] Wolpert had previously derived no free lunch theorems for machine learning (statistical inference).[2]

In 2005, Wolpert and Macready themselves indicated that the first theorem in their paper "state[s] that any two optimization algorithms are equivalent when their performance is averaged across all possible problems".[3]

The "no free lunch" (NFL) theorem is an easily stated and easily understood consequence of theorems Wolpert and Macready actually prove. It is weaker than the proven theorems, and thus does not encapsulate them. Various investigators have extended the work of Wolpert and Macready substantively. In terms of how the NFL theorem is used in the context of the research area, the no free lunch in search and optimization is a field that is dedicated for purposes of mathematically analyzing data for statistical identity, particularly search[4] and optimization.[1]

While some scholars argue that NFL conveys important insight, others argue that NFL is of little relevance to machine learning research.[5][6][7]

  1. ^ a b Wolpert, D. H.; Macready, W. G. (1997). "No Free Lunch Theorems for Optimization". IEEE Transactions on Evolutionary Computation. 1: 67–82. CiteSeerX 10.1.1.138.6606. doi:10.1109/4235.585893. S2CID 5553697.
  2. ^ Wolpert, David (1996), "The Lack of A Priori Distinctions between Learning Algorithms", Neural Computation, pp. 1341–1390. Archived 2016-12-20 at the Wayback Machine
  3. ^ Wolpert, D.H.; Macready, W.G. (December 2005). "Coevolutionary Free Lunches". IEEE Transactions on Evolutionary Computation. 9 (6): 721–735. doi:10.1109/TEVC.2005.856205. hdl:2060/20050082129. ISSN 1089-778X.
  4. ^ Wolpert, D. H.; Macready, W. G. (1995). "No Free Lunch Theorems for Search". Technical Report SFI-TR-95-02-010. Santa Fe Institute. S2CID 12890367.
  5. ^ Whitley, Darrell; Watson, Jean Paul (2005). Burke, Edmund K.; Kendall, Graham (eds.). Complexity Theory and the No Free Lunch Theorem. Boston, MA: Springer US. pp. 317–339. doi:10.1007/0-387-28356-0_11. ISBN 978-0-387-23460-1.
  6. ^ Giraud-Carrier, Christophe, and Foster Provost. "Toward a justification of meta-learning: Is the no free lunch theorem a show-stopper." In Proceedings of the ICML-2005 Workshop on Meta-learning, pp. 12–19. 2005.
  7. ^ Goldblum, M., Finzi, M., Keefer, R., and Wilson, AG. "The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning." In Proceedings of the International Conference on Machine Learning, 2024.