Editing No free lunch in search and optimization

{{Short description|Average solution cost is the same with any method}}
{{about|mathematical analysis of computing|associated folklore and broad implications of the theorem|No free lunch theorem}}

[[File:No free lunch theorems figure.png|right|thumb|305px|The problem is to rapidly find a solution among candidates a, b, and c that is as good as any other, where goodness is either 0 or 1. There are eight instances ("lunch plates") f''xyz'' of the problem, where ''x,'' ''y,'' and ''z'' indicate the goodness of a, b, and c, respectively. Procedure ("restaurant") A evaluates candidates in the order a, b, c, and B evaluates candidates in reverse that order, but each "charges" 1 evaluation in 5 cases, 2 evaluations in 2 cases, and 3 evaluations in 1 case.]]

<!--

This figure contradicts the text of the article, and uses terms that are not defined in the article.

[[File:Effects of NFL Therorem.PNG|right|thumb|450px|Graphical explanation of the consequences of the NFL theorems for [[heuristic algorithm]]s: all heuristics have the same average performance. A given heuristic may outperform another one for a given problem or problem domain, but it will be worse in others problem domains. Furthermore, the better it is in that domain, the worse it will be in other domains]]

-->
In [[Computational complexity theory|computational complexity]] and [[optimization (mathematics)|optimization]] the '''no free lunch theorem''' is a result that states that for certain types of mathematical problems, the [[computational cost]] of finding a solution, averaged over all problems in the class, is the same for any solution method. The name alludes to the saying "[[no such thing as a free lunch]]", that is, no method offers a "short cut".  This is under the assumption that the search space is a [[probability density function]]. It does not apply to the case where the search space has underlying structure (e.g., is a differentiable function) that can be exploited more efficiently (e.g., [[Newton's method in optimization]]) than random search or even has closed-form solutions (e.g., the extrema of a quadratic polynomial) that can be determined without search at all. For such probabilistic assumptions, the outputs of all procedures solving a particular type of problem are statistically identical. A colourful way of describing such a circumstance, introduced by [[David Wolpert]] and [[William G. Macready]] in connection with the problems of search<ref name=WM95>{{cite journal |last1=Wolpert |first1=D. H. |last2=Macready |first2=W. G. |year=1995 |title=No Free Lunch Theorems for Search |journal=Technical Report SFI-TR-95-02-010 |publisher=Santa Fe Institute |s2cid=12890367 }}</ref> and optimization,<ref name="WM97">{{cite journal |last1=Wolpert |first1=D. H. |last2=Macready |first2=W. G. |year=1997 |title=No Free Lunch Theorems for Optimization |url=https://ieeexplore.ieee.org/document/585893 |journal=IEEE Transactions on Evolutionary Computation |volume=1 |pages= 67–82|doi=10.1109/4235.585893|s2cid=5553697 |citeseerx=10.1.1.138.6606 }}</ref>
is to say that  [[TANSTAAFL|there is no free lunch]]. Wolpert had previously derived no free lunch theorems for [[machine learning]] ([[statistical inference]]).<ref name=Wolpert96>{{cite book |last=Wolpert |first=David |year=1996 |chapter=The Lack of A Priori Distinctions between Learning Algorithms |title=Neural Computation |volume=8 |issue=7 |pages=1341–1390 |doi=10.1162/neco.1996.8.7.1341 |s2cid=207609360 }}</ref> 
Before Wolpert's article was published, Cullen Schaffer independently proved a restricted version of one of Wolpert's theorems and used it to critique the current state of machine learning research on the problem of induction.<ref name=Schaffer94>{{cite book |last=Schaffer |first=Cullen |year=1994 |chapter-url=http://dml.cs.byu.edu/~cgc/docs/mldm_tools/Reading/LCG.pdf |chapter=A conservation law for generalization performance |title=International Conference on Machine Learning |editor-first=H. |editor-last=Willian |editor2-first=W. |editor2-last=Cohen |location=San Francisco |publisher=Morgan Kaufmann |pages=259–265 }}</ref>

In the "no free lunch" [[metaphor]], each "restaurant" (problem-solving procedure) has a "menu" associating each "lunch plate" (problem) with a "price" (the performance of the procedure in solving the problem). The menus of restaurants are identical except in one regard – the prices are shuffled from one restaurant to the next. For an [[omnivore]] who is as likely to order each plate as any other, the average cost of lunch does not depend on the choice of restaurant. But a [[vegan]] who goes to lunch regularly with a [[carnivore]] who seeks economy might pay a high average cost for lunch. To methodically reduce the average cost, one must use advance knowledge of a) what one will order and b) what the order will cost at various restaurants. That is, improvement of performance in problem-solving hinges on using prior information to match procedures to problems.<ref name=WM97/><ref name=Schaffer94/>

In formal terms, there is no free lunch when the [[probability distribution]] on problem instances is such that all problem solvers have identically distributed results. In the case of [[search algorithm|search]], a problem instance in this context is a particular [[objective function]], and a result is a [[sequence]] of values obtained in evaluation of [[candidate solutions]] in the [[function domain|domain]] of the function. For typical interpretations of results, search is an [[Optimization (mathematics)|optimization]] process. There is no free lunch in search if and only if the distribution on objective functions is [[invariant (mathematics)|invariant]] under [[permutation]] of the space of candidate solutions.<!-- 
--><ref name=Streeter>Streeter, M. (2003) "[https://www.cs.york.ac.uk/rts/docs/GECCO_2003/papers/2724/27241418.pdf Two Broad Classes of Functions for Which a No Free Lunch Result Does Not Hold]," ''Genetic and Evolutionary Computation – GECCO 2003'', pp. 1418–1430.</ref><!--
--><ref name=Igel>Igel, C., and Toussaint, M. (2004) "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.158.9715&rep=rep1&type=pdf A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions]," ''Journal of Mathematical Modelling and Algorithms'' '''3''', pp. 313–322.</ref><!--
--><ref name="English2004">English, T. (2004) [https://sites.google.com/site/boundedtheoretics/CEC04.pdf No More Lunch: Analysis of Sequential Search], ''Proceedings of the 2004 IEEE Congress on Evolutionary Computation'', pp. 227–234.</ref> This condition does not hold precisely in practice,<ref name=Igel/> but an "(almost) no free lunch" theorem suggests that it holds approximately.<ref name=ANFL>S. Droste, T. Jansen, and I. Wegener. 2002. "[https://www.sciencedirect.com/science/article/pii/S0304397502000944/pdf?md5=4464a32c6ad989dbea47d759973008dc&pid=1-s2.0-S0304397502000944-main.pdf&_valck=1 Optimization with randomized search heuristics: the (A)NFL theorem, realistic scenarios, and difficult functions]," ''Theoretical Computer Science,'' vol. 287, no. 1, pp. 131–144.</ref>

==Overview==

Some computational problems are solved by searching for good solutions in a space of [[candidate solution]]s. A description of how to repeatedly select candidate solutions for evaluation is called a [[search algorithm]]. On a particular problem, different search algorithms may obtain different results, but over all problems, they are indistinguishable. It follows that if an algorithm achieves superior results on some problems, it must pay with inferiority on other problems. In this sense there is [[no free lunch]] in search.<ref name=WM95/> Alternatively, following Schaffer,<ref name=Schaffer94/> search performance is [[Conservation law (physics)|conserved]]. Usually search is interpreted as [[Optimization (mathematics)|optimization]], and this leads to the observation that there is no free lunch in optimization.<ref name=WM97/>

"The 'no free lunch' theorem of Wolpert and Macready," as stated in plain language by Wolpert and Macready themselves, is that "any two algorithms are equivalent when their performance is averaged across all possible problems."<ref name=WM-coev>Wolpert, D.H., and Macready, W.G. (2005) "[https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20060007558.pdf Coevolutionary free lunches]," ''IEEE Transactions on Evolutionary Computation'', 9(6): 721–735</ref> The "no free lunch" results indicate that matching algorithms to problems gives higher average performance than does applying a fixed algorithm to all.{{Citation needed|date=April 2019}}  Igel and Toussaint<ref name=Igel/> and English<ref name=English2004/> have established a general condition under which there is no free lunch. While it is physically possible, it does not hold precisely.<ref name=Igel/> Droste, Jansen, and Wegener have proved a theorem they interpret as indicating that there is "(almost) no free lunch" in practice.<ref name=ANFL/>

To make matters more concrete, consider an optimization practitioner confronted with a problem. Given some knowledge of how the problem arose, the practitioner may be able to exploit the knowledge in selection of an algorithm that will perform well in solving the problem. If the practitioner does not understand how to exploit the knowledge, or simply has no knowledge, then he or she faces the question of whether some algorithm generally outperforms others on real-world problems. The authors of the "(almost) no free lunch" theorem say that the answer is essentially no, but admit some reservations as to whether the theorem addresses practice.<ref name=ANFL/>

==Theorems==

A "problem" is, more formally, an [[objective function]] that associates [[candidate solution]]s with goodness values. A [[search algorithm]] takes an objective function as input and evaluates candidate solutions one-by-one. The output of the algorithm is the [[sequence]] of observed goodness values.<ref>A search algorithm also outputs the sequence of candidate solutions evaluated, but that output is unused in this article.</ref><ref name=English2000>{{cite book |last=English |first=T. M. |title=Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512) |chapter=Optimization is easy and learning is hard in the typical function |year=2000 |volume=2 |pages=924–931 |doi=10.1109/CEC.2000.870741 |isbn=0-7803-6375-2 |s2cid=11295575 }}</ref>

Wolpert and Macready stipulate that an algorithm never reevaluates a candidate solution, and that algorithm performance is measured on outputs.<ref name=WM97/>  For simplicity, we disallow randomness in algorithms. Under these conditions, when a search algorithm is run on every possible input, it generates each possible output exactly once.<ref name=English2004/> Because performance is measured on the outputs, the algorithms are indistinguishable in how often they achieve particular levels of performance.

Some measures of performance indicate how well search algorithms do at [[Optimization (mathematics)|optimization]] of the objective function. Indeed, there seems to be no interesting application of search algorithms in the class under consideration but to optimization problems. A common performance measure is the least index of the least value in the output sequence. This is the number of evaluations required to minimize the objective function. For some algorithms, the time required to find the minimum is proportional to the number of evaluations.<ref name=English2004/>

The original no free lunch (NFL) theorems assume that all objective functions are equally likely to be input to search algorithms.<ref name=WM97/> It has since been established that there is NFL if and only if, loosely speaking, "shuffling" objective functions has no impact on their probabilities.<ref name=Igel/><ref name=English2004/> Although this condition for NFL is physically possible, it has been argued that it certainly does not hold precisely.<ref name=Igel/>

The obvious interpretation of "not NFL" is "free lunch," but this is misleading. NFL is a matter of degree, not an all-or-nothing proposition. If the condition for NFL holds approximately, then all algorithms yield approximately the same results over all objective functions.<ref name=English2004/> "Not NFL" implies only that algorithms are inequivalent overall by ''some'' measure of performance. For a performance measure of interest, algorithms may remain equivalent, or nearly so.<ref name=English2004/>

===Kolmogorov randomness===

Almost all elements of the set of all possible functions (in the set-theoretic sense of "function") are [[Kolmogorov randomness|Kolmogorov random]], and hence the NFL theorems apply to a set of functions almost all of which cannot be expressed more compactly than as a lookup table that contains a distinct (and random) entry for each point in the search space. Functions that can be expressed more compactly (for example, by a mathematical expression of reasonable size) are by definition not Kolmogorov random.

Further, within the set of all possible objective functions, levels of goodness are equally represented among candidate solutions, hence good solutions are scattered throughout the space of candidates. Accordingly, a search algorithm will rarely evaluate more than a small fraction of the candidates before locating a very good solution.<ref name=English2000/>

Almost all objective functions are of such high [[Kolmogorov complexity]] that they cannot be stored in a particular computer.<ref name=Streeter/><ref name=English2004/><ref name=English2000/> More precisely, if we model a given physical computer as a register machine with a given size memory on the order of the memories of modern computers, then most objective functions cannot be stored in their memories. There is more information in the typical objective function or algorithm than [[Seth Lloyd]] estimates the observable universe is capable of registering.<ref name=Lloyd2002>{{cite journal |last=Lloyd |first=S. |year=2002 |title=Computational capacity of the universe |journal=Physical Review Letters |volume=88 |issue=23 |pages=237901–237904 |doi=10.1103/PhysRevLett.88.237901 |pmid=12059399 |arxiv=quant-ph/0110141 |bibcode=2002PhRvL..88w7901L |s2cid=6341263 }}</ref> For instance, if each candidate solution is encoded as a sequence of 300 0's and 1's, and the goodness values are 0 and 1, then most objective functions have Kolmogorov complexity of at least 2<sup>300</sup> bits,<ref name=LV>{{cite book |last1=Li |first1=M. |last2=Vitányi |first2=P. |year=1997 |title=An Introduction to Kolmogorov Complexity and Its Applications |edition=2nd |location=New York |publisher=Springer |isbn=0-387-94868-6 }}</ref> and this is greater than Lloyd's bound of 10<sup>90</sup> ≈ 2<sup>299</sup> bits. It follows that the original "no free lunch" theorem does not apply to what can be stored in a physical computer; instead the so-called "tightened" no free lunch theorems need to be applied. It has also been shown that NFL results apply to incomputable functions.<ref>{{cite book |last=Woodward |first=John R. |chapter-url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.158.7782&rep=rep1&type=pdf |chapter=Computable and incomputable functions and search algorithms |title=IEEE International Conference on Intelligent Computing and Intelligent Systems, 2009 |volume=1 |pages=871–875 |year=2009 |publisher=IEEE |citeseerx=10.1.1.158.7782 }}</ref>

==Formal synopsis==

<math>Y^X</math> is the set of all [[objective function]]s ''f'':''X''→''Y'', where <math>X</math> is a finite [[solution space]] and <math>Y</math> is a finite [[poset]]. The set of all [[permutation]]s of ''X'' is ''J''. A [[random variable]] ''F'' is distributed on <math>Y^X</math>. For all ''j'' in ''J'', ''F'' o ''j'' is a random variable distributed on <math>Y^X</math>, with P(''F'' o ''j'' = ''f'') = P(''F'' = ''f'' o ''j''<sup>−1</sup>) for all ''f'' in <math>Y^X</math>.

Let ''a''(''f'') denote the output of search algorithm ''a'' on input ''f''. If ''a''(''F'') and ''b''(''F'') are identically distributed for all search algorithms ''a'' and ''b'', then ''F'' has an ''NFL distribution''. This condition holds if and only if ''F'' and ''F'' o ''j'' are identically distributed for all ''j'' in ''J''.<ref name=Igel/><ref name=English2004/> In other words, there is no free lunch for search algorithms if and only if the distribution of objective functions is invariant under permutation of the solution space.<ref>The "only if" part was first published by {{cite thesis |first=C. W. |last=Schumacher |type=PhD dissertation |title=Black Box Search : Framework and Methods |publisher=The University of Tennessee, Knoxville |year=2000 |id={{ProQuest|304620040}} }}</ref> Set-theoretic NFL theorems have recently been generalized to arbitrary cardinality <math>X</math> and <math>Y</math>.<ref name=Rowe>{{cite journal |last1=Rowe |last2=Vose |last3=Wright |url=https://scholarworks.umt.edu/cgi/viewcontent.cgi?article=1008&context=cs_pubs |title=Reinterpreting No Free Lunch |journal=Evolutionary Computation |year=2009 |volume=17 |issue=1 |pages=117–129 |doi=10.1162/evco.2009.17.1.117 |pmid=19207090 |s2cid=6251842 }}</ref>

==Origin==

Wolpert and Macready give two principal NFL theorems, the first regarding objective functions that do not change while search is in progress, and the second regarding objective functions that may change.<ref name=WM97/>

:''Theorem 1'': For any pair of algorithms ''a''<sub>1</sub> and ''a''<sub>2</sub>
::<math>\sum_f P(d_m^y | f, m, a_1) = \sum_f P(d_m^y | f, m, a_2),</math> where <math>d_m^y</math> denotes the ordered set of size <math>m</math> of the cost values <math>y \in Y</math> associated to input values <math>x \in X</math>, <math>f:X \rightarrow Y </math> is the function being optimized and <math>P(d_m^y | f, m, a)</math> is the [[conditional probability]] of obtaining a given sequence of cost values from algorithm <math>a</math> run <math>m</math> times on function <math>f</math>.

In essence, this says that when all functions ''f'' are equally likely, the probability of observing an arbitrary sequence of ''m'' values in the course of search does not depend upon the search algorithm.

The second theorem establishes a "more subtle" NFL result for time-varying objective functions.<ref name="WM97" />

==Interpretations of results==

A conventional, but not entirely accurate, interpretation of the NFL results is that "a general-purpose universal optimization strategy is theoretically impossible, and the only way one strategy can outperform another is if it is specialized to the specific problem under consideration".<ref>{{cite journal |last1=Ho |first1=Y. C. |last2=Pepyne |first2=D. L. |year=2002 |title=Simple Explanation of the No-Free-Lunch Theorem and Its Implications |journal=Journal of Optimization Theory and Applications |volume=115 |issue=3 |pages=549–570 |doi=10.1023/A:1021251113462 |s2cid=123041865 }}</ref> Several comments are in order:

*''A general-purpose almost-universal optimizer exists theoretically.'' Each search algorithm performs well on almost all objective functions.<ref name=English2000/> So if one is not concerned with the "relatively small" differences between search algorithms, e.g., because computer time is cheap, then you shouldn't worry about no free lunch.
*''An algorithm may outperform another on a problem when neither is specialized to the problem.'' Indeed, it may be that both algorithms are among the worst for the problem. More generally, Wolpert and Macready have developed a measure of the degree of "alignment" between an algorithm and a distribution over problems (strictly speaking, an inner product).<ref name=WM97/> To say that one algorithm matches a distribution better than another is not to say that either has been consciously specialized to the distribution; an algorithm may have good alignment just by luck.
*''In practice, some algorithms reevaluate candidate solutions.'' The reason to only consider performance on never-before-evaluated candidates is to make sure that in comparing algorithms one is comparing apples to apples. Moreover, any superiority of an algorithm that never reevaluates candidates over another algorithm that does on a particular problem may have nothing to do with specialization to the problem.
*''For almost all objective functions, specialization is essentially accidental.'' Incompressible, or [[Kolmogorov randomness|Kolmogorov random]], objective functions have no regularity for an algorithm to exploit, as far as the universal Turing machining used to define Kolmogorov randomness is concerned. So presume that there is one, clearly superior choice of universal Turing machine. Then given an objective function that is incompressible for that Turing machine, there is no basis for choosing between two algorithms if both are compressible, as measured using that Turing machine. If a chosen algorithm performs better than most, the result is happenstance.<ref name=English2000 /> A Kolmogorov random function has no representation smaller than a lookup table that contains a (random) value corresponding to each point in the search space; ''any'' function that can be expressed more compactly is, by definition, not Kolmogorov random.

In practice, only highly compressible (far from random) objective functions fit in the storage of computers, and it is not the case that each algorithm performs well on almost all compressible functions. There is generally a performance advantage in incorporating prior knowledge of the problem into the algorithm. While the NFL results constitute, in a strict sense, [[full employment theorem]]s for optimization professionals, it is important to bear the larger context in mind. For one thing, humans often have little prior knowledge to work with. For another, incorporating prior knowledge does not give much of a performance gain on some problems. Finally, human time is very expensive relative to computer time. There are many cases in which a company would choose to optimize a function slowly with an unmodified computer program rather than rapidly with a human-modified program.

The NFL results do not indicate that it is futile to take "pot shots" at problems with unspecialized algorithms. No one has determined the fraction of practical problems for which an algorithm yields good results rapidly. And there is a practical free lunch, not at all in conflict with theory. Running an implementation of an algorithm on a computer costs very little relative to the cost of human time and the benefit of a good solution. If an algorithm succeeds in finding a satisfactory solution in an acceptable amount of time, a small investment has yielded a big payoff. If the algorithm fails, then little is lost.

Recently some philosophers of science have argued that there are ways to circumvent the no free lunch theorems, by using "meta-induction". Wolpert addresses these arguments in 
<!-- 
--><ref name="WOLP23">{{cite journal |last1=Wolpert |first1=D. H. |year=2023 |title=The Implications of the No-Free-Lunch Theorems for Meta-induction |url=https://doi.org/10.1007/s10838-022-09609-2 |
journal=Journal for General Philosophy of Science |volume=1 |pages= 67–82|doi=10.1109/4235.585893|s2cid=5553697 }}</ref><!-- 
-->.

==Coevolution==

Wolpert and Macready have proved that there are [[free lunch]]es in [[coevolution]]ary optimization.<ref name=WM-coev/> Their analysis "covers 'self-play' problems. In these problems, the set of players work together to produce a champion, who then engages one or more antagonists in a subsequent multiplayer game."<ref name=WM-coev/> That is, the objective is to obtain a good player, but without an objective function. The goodness of each player (candidate solution) is assessed by observing how well it plays against others. An algorithm attempts to use players and their quality of play to obtain better players. The player deemed best of all by the algorithm is the champion. Wolpert and Macready have demonstrated that some coevolutionary algorithms are generally superior to other algorithms in quality of champions obtained. Generating a champion through self-play is of interest in [[evolutionary computation]] and [[game theory]]. The results are inapplicable to coevolution of biological species, which does not yield champions.<ref name=WM-coev/>

==See also==
* [[Inductive bias]]
* [[Occam's razor]]
* [[Simplicity]]
* [[Ugly duckling theorem]]

== Notes ==
{{reflist|30em}}

==External links==
* http://www.no-free-lunch.org
*[http://citeseer.ist.psu.edu/radcliffe95fundamental.html Radcliffe and Surry, 1995, "Fundamental Limitations on Search Algorithms: Evolutionary Computing in Perspective" (an early published paper on NFL, appearing soon after Schaffer's ICML paper, which in turn was based on Wolpert's preprint; available in various formats)]
*[http://boundedtheoretics.com/bt/Publications.php NFL publications by Thomas English]
*[http://www.neuroinformatik.ruhr-uni-bochum.de/PEOPLE/igel/publications.html NFL publications by Christian Igel and Marc Toussaint]
*[https://www.cs.colostate.edu/~genitor/Pubs.html NFL and "free lunch" publications by Darrell Whitley]
*[http://ti.arc.nasa.gov/profile/dhw/optimization/ Old list of publications by David Wolpert, William Macready, and Mario Koeppen on optimization and search]

[[Category:Mathematical optimization]]
[[Category:Theorems in computational complexity theory]]