# Understanding the No Free Lunch Theorem

I came across the No Free Lunch Theorem via Jürgen Schmidhuber's paper on Universal Search and there were a couple remarks on NFL which stood out to me. The first was that we can't define a uniform distribution on an infinite number of objects. Second, Schmidhuber argues that there's nothing inherently natural about the uniform distribution and I'm inclined to agree on this point as well.

Although I'm aware of maximum-entropy arguments in favour of uniform distributions, on an infinite number of objects it's more natural to observe an exponential distribution. Might there be a well-known counter-argument in the optimisation literature to the points raised by Jürgen Schmidhuber?

• Jürgen Schmidhuber is right: "I don't like the No Free Lunch Theorems for Optimization, because their assumptions are unrealistic and useless in practice, but the theorem itself certainly feels true (but in a less trivial way than what is actually proved). And the conclusion is deeply flawed. It claims that there is no difference between a buggy implementation of a flawed heuristic and a correct implementation of a reasonable solution strategy. The conclusion should rather be that ..." – Thomas Klimpel Nov 22 '17 at 0:45
• @ThomasKlimpel Where did Schmidhuber write this? – Martin Berger Nov 22 '17 at 11:48
• @MartinBerger I must say that I was a bit confused myself when I first read this. These are merely Klimpel's reflections which are similar in spirit to Schmidhuber's criticism. – Aidan Rocke Nov 22 '17 at 15:12

You're asking about optimization and universal search, BUT machine-learning is tagged and you're wondering about "a uniform distribution on an infinite" discrete set so perhaps this will be helpful. There's a classic No-Free-Lunch result in PAC learning which says that you cannot learn the concept class of all boolean functions on the integers in a distribution-free fashion. Meaning: there is no function $m=m(\epsilon,\delta)$ such that if you request $m$ or more iid labeled examples from any unknown distribution, you'll be able to guarantee an $\epsilon$-accurate classifier with $\delta$-confidence. The proof proceeds by taking a uniform distribution over a large enough support size -- big enough to thwart any given purported sample complexity $m(\epsilon,\delta)$. A shorthand for saying this might be "take the uniform distribution over the integers". Now we all know that's absurd, and the explanation above is the only way I know to make sense out of it (and also jibes with the No-Free-Lunch context).