Open main menu

Wikipedia β

No free lunch theorem

In mathematical folklore, the "no free lunch" theorem (sometimes pluralized) of David Wolpert and William Macready appears 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 1997 theorems of Wolpert and Macready are mathematically technical and some find them unintuitive.

The folkloric "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. See No free lunch in search and optimization for treatment of the research area.


Original NFL theoremsEdit

Wolpert and Macready give two NFL theorems that are closely related to the folkloric theorem. In their paper, they state:

We have dubbed the associated results NFL theorems because they demonstrate that if an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems.[1]

The first theorem first hypothesizes that objective functions do not change while optimization is in progress, and then hypothesizes that objective functions may change.[1]

Theorem 1: For any algorithms a1 and a2, at iteration step m

where   denotes the ordered set of size   of the cost values   associated to input values  ,   is the function being optimized and   is the conditional probability of obtaining a given sequence of cost values from algorithm   run   times on function  .

The theorem can be equivalently formulated as follows:

Theorem 1: Given a finite set   and a finite set   of real numbers, assume that   is chosen at random according to uniform distribution on the set   of all possible functions from   to  . For the problem of optimizing   over the set  , then no algorithm performs better than blind search.

Here, blind search means that at each step of the algorithm, the element   is chosen at random with uniform probability distribution from the elements of   that have not been chosen previously.

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 optimization does not depend upon the algorithm. In the analytic framework of Wolpert and Macready, performance is a function of the sequence of observed values (and not e.g. of wall-clock time), so it follows easily that all algorithms have identically distributed performance when objective functions are drawn uniformly at random, and also that all algorithms have identical mean performance. But identical mean performance of all algorithms does not imply Theorem 1, and thus the folkloric theorem is not equivalent to the original theorem.

Theorem 2 establishes a similar, but "more subtle", NFL result for time-varying objective functions.[1]


The NFL theorems were explicitly not motivated by the question of what can be inferred (in the case of NFL for machine learning) or found (in the case of NFL for search) when the "environment is uniform random". Rather uniform randomness was used as a tool, to compare the number of environments for which algorithm A outperforms algorithm B to the number of environments for which B outperforms A. NFL tells us that (appropriately weighted) there are just as many environments in both of those sets.

This is true for many definitions of what precisely an "environment" is. In particular, there are just as many prior distributions (appropriately weighted) in which learning algorithm A beats B (on average) as vice-versa. This statement about sets of priors is what is most important about NFL, not the fact that any two algorithms perform equally for the single, specific prior distribution that assigns equal probability to all environments.

While the NFL is important to understand the fundamental limitation for a set of problems, it does not state anything about each particular instance of a problem that can arise in practice. That is, the NFL states what the NFL states in the mathematical statements and it is nothing more than that. For example, it applies to the situations where the algorithm is fixed first and a nature can choose a worst problem instance to each fixed algorithm. Therefore, if we have a "good" problem in practice or if we can choose a "good" learning algorithm for a given particular problem instance, then the NFL does not mention any limitation about this particular problem instance. See for example [4]. To understand the results of the NFL along with "seemingly" contradicting results from other papers, it is important to actually understand the mathematical logic of the NFL instead of intuitive notation of the NFL. All results including the NFL and [4] are indeed consistent.

Implications for the scientific methodEdit

To illustrate one of the counter-intuitive implications of NFL, suppose we fix two supervised learning algorithms, C and D. We then sample a target function f to produce a set of input-output pairs, d. How should we choose whether to train C or D on d, in order to make predictions for what output would be associated with a point lying outside of d?

It is common in almost of all science and statistics to answer this question - to choose between C and D - by running cross-validation on d with those two algorithms. In other words, to decide whether to generalize from d with either C or D, we see which of them has better out-of-sample performance when tested within d.

Note that since C and D are fixed, this use of cross-validation to choose between them is itself an algorithm, i.e., a way of generalizing from an arbitrary dataset. Call this algorithm A. (Arguably, A is a simplified model of the scientific method itself.)

Note as well though that we could also use anti-cross-validation to make our choice. In other words, we could choose between C and D based on which has worse out-of-sample performance within d. Again, since C and D are fixed, this use of anti-cross-validation is itself an algorithm. Call that algorithm B.

NFL tells us (loosely speaking) that B must beat A on just as many target functions (and associated datasets d) as A beats B. In this very specific sense, the scientific method will lose to the "anti" scientific method just as readily as it wins.[5]


  1. ^ a b c d Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization", IEEE Transactions on Evolutionary Computation 1, 67.
  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., and Macready, W.G. (2005) "Coevolutionary free lunches", IEEE Transactions on Evolutionary Computation, 9(6): 721-735
  4. ^ a b Kawaguchi, K., Kaelbling, L.P, and Bengio, Y.(2017) "Generalization in deep learning",
  5. ^ Wolpert, D.H. (2013) "What the no free lunch theorems really mean", Ubiquity, Volume 2013, December 2013, DOI: 10.1145/2555235.2555237

4. Wolpert, D.H. (2013) "What the no free lunch theorems really mean", Ubiquity, Volume 2013, December 2013, DOI: 10.1145/2555235.2555237

External linksEdit