No Free Lunch Theorem - Original NFL Theorems

Original NFL Theorems

Wolpert and Macready give two NFL theorems that are closely related to the folkloric theorem. The first hypothesizes objective functions that do not change while optimization is in progress, and the second hypothesizes objective functions that may change.

Theorem 1: For any pair of algorithms a₁ and a₂

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