5
$\begingroup$

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?

  1. Optimal Ordered Problem Solver
  2. No Free Lunch Theorem
Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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 ..." $\endgroup$
    – Thomas Klimpel
    Nov 22, 2017 at 0:45
  • $\begingroup$ @ThomasKlimpel Where did Schmidhuber write this? $\endgroup$
    – Martin Berger
    Nov 22, 2017 at 11:48
  • $\begingroup$ @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. $\endgroup$
    – Aidan Rocke
    Nov 22, 2017 at 15:12

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.