Is the No Free Lunch Theorem (NFL) relevant in practice?

Let us consider the set of all (possible) functions R^n\to R discretized with two bytes per real number.1 Let us call this set F. The No Free Lunch Theorem2 holds for this set of functions because the set is closed under permutation. The number of functions in F is approximately3

|F| = \left(10^5\right)^{\left(10^5\right)^n} = 10^{5\times10^{5n}} = 10^{5\times 100000^{n}}

Let us put the size of F into perspective. The number of electrons in the universe multiplied by the number of Planck times passed since the beginning of time is about 10^{141}.4 This number is minuscule compared to |F|=10^{5\times 100000^{n}}. Hence, the number of real world functions, and in particular the number of real world functions we could possibly ever encounter (and hence could possibly be relevant to us) is minuscule compared the number of functions contained in F.

Does NFL hold for any practically relevant (and nontrivial) subset of F? Does NFL hold for any practically relevant nontrivial set of functions? We don’t know, but it looks exceedingly unlikely to us.

Footnotes

  1. As an example, this gives roughly 5 digits of precision for representing numbers from the [0,1] interval. In some practical situations we may require more precision or a wider range. Hence, the following size derivation is on the conservative side.↩︎

  2. NFL states that aggregated over all functions, all search algorithms perform identical (given they do not revisit solutions). This is true when the set of functions is closed under permutation. See Wolpert, D.H. and Macready, W.G., 2002. No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1), pp.67-82.↩︎

  3. The number of functions equals the number of different function values to the power of the number of different solutions.↩︎

  4. The number of electrons (or atoms) in the universe is about 10^{80}. The age of the universe is about 10^{18} seconds. The Planck time is about 10^{-43} seconds. The number of all electrons in the universe multiplied by the number of Planck times since the beginning of the universe is about 10^{80} \times 10^{61} = 10^{141}.↩︎