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". Wolpert had previously derived no free lunch theorems for machine learning (statistical inference).

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". 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.

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.

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

where $d_{m}^{y}$ $d_{m}^{y}$ denotes the ordered set of size $m$ $m$ of the cost values $y$ $y$ associated to input values $x\in X$ $x\in X$ , $f:X\rightarrow Y$ $f:X\rightarrow Y$ is the function being optimized and $P(d_{m}^{y}|f,m,a)$ $P(d_{m}^{y}|f,m,a)$ is the conditional probability of obtaining a given sequence of cost values from algorithm $a$ $a$ run $m$ $m$ times on function $f$ $f$ .

...
Wikipedia