No Free Lunch Theorems

Broadly speaking, there are two no free lunch theorems. One for supervised machine learning (Wolpert 1996) and one for search/optimization (Wolpert and Macready 1997). For an overview of the (no) free lunch and associated theorems, see David Wolpert’s What does dinner cost?

No Free Lunch Theorems

Hume (1739–1740) pointed out that ‘even after the observation of the frequent or constant conjunction of objects, we have no reason to draw any inference concerning any object beyond those of which we have had experience’. More recently, and with increasing rigour, Mitchell (1980), Schaffer (1994) and Wolpert (1996) showed that bias-free learning is futile. Wolpert (1996) shows that in a noise-free scenario where the loss function is the misclassification rate, if one is interested in off-training-set error, then there are no a priori distinctions between learning algorithms.

More formally, where

d = training set;

m = number of elements in training set;

f = ‘target’ input-output relationships;

h = hypothesis (the algorithm's guess for f made in response to d); and

C = off-training-set ‘loss’ associated with f and h (‘generalization error’)

all algorithms are equivalent, on average, by any of the following measures of risk: E(C|d), E(C|m), E(C|f,d), or E(C|f,m).

How well you do is determined by how ‘aligned’ your learning algorithm P(h|d) is with the actual posterior, P(f|d). Wolpert's result, in essence, formalizes Hume, extends him and calls the whole of science into question.

No Free Lunch for Search/Optimization

The no free lunch theorem for search and optimization (Wolpert and Macready 1997) applies to finite spaces and algorithms that do not resample points. All algorithms that search for an extremum of a cost function perform exactly the same when averaged over all possible cost functions. So, for any search/optimization algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class.

Free Lunches

- Second moments and higher of algorithms' generalization error

- Coevolution (Wolpert and Macready 2005)

- Confidence intervals can give a priori distinctions between algorithms

Quotes

"We show that all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions. In particular, if algorithm A outperforms algorithm B on some cost functions, then loosely speaking there must exist exactly as many other functions where B outperforms A." Wolpert and Macready (1995)

"A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving. A number of "no free lunch" (NFL) theorems are presented that establish that for any algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class." Wolpert and Macready (1997)