<p>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 <em>any</em> 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).</p>

CC BY-SA 3.0
2017-11-22T13:48:02.857Z
2017-11-22T16:02:33.290Z
2017-11-22T16:02:33.290Z
Aryeh
<p>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. </p>

<p>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? </p>

<ol>
<li><a href="https://arxiv.org/abs/cs/0207097" rel="nofollow noreferrer">Optimal Ordered Problem Solver</a></li>
<li><a href="https://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf" rel="nofollow noreferrer">No Free Lunch Theorem</a></li>
</ol>

CC BY-SA 3.0
2017-11-22T00:45:51.557Z
[Jürgen Schmidhuber is right](https://mathoverflow.net/questions/176472/negative-impact-of-wrong-or-non-rigorous-proofs/176646#176646): "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
CC BY-SA 3.0
2017-11-22T11:48:35.010Z
@ThomasKlimpel Where did Schmidhuber write this?
Martin Berger
CC BY-SA 3.0
2017-11-22T15:12:26.413Z
@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
<optimization><machine-learning>
Understanding the No Free Lunch Theorem
Aidan Rocke
# Understanding the No Free Lunch Theorem

(Asked by: username_0 on 2017-11-21)

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](https://arxiv.org/abs/cs/0207097)
2. [No Free Lunch Theorem](https://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf)

**Tags:** optimization, machine-learning

> **Comments:**
> **username_1**: [Jürgen Schmidhuber is right](https://mathoverflow.net/questions/176472/negative-impact-of-wrong-or-non-rigorous-proofs/176646#176646): "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 ..."  
> **username_2**: @ThomasKlimpel Where did Schmidhuber write this?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_3 on 2017-11-22. Score: 5 | Accepted answer

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


---

