<p>Your guess is correct. The proof of No Free Lunch constructs a distribution over a large domain (comparable to <span class="math-container">$m$</span>), and it considers a hypothesis class containing all functions on that domain (about <span class="math-container">$2^m$</span> of them). It then shows hardness of learning for that setting. So if we have an infinite domain and the corresponding infinite hypothesis class, then for every finite <span class="math-container">$m$</span>, we get an impossibility result. So that infinite class is not PAC learnable.</p>
<p>But if we have a finite hypothesis class, then there will be some large enough <span class="math-container">$m$</span> where this construction won't work, since it would require constructing more hypotheses (about <span class="math-container">$2^m$</span> of them) than are actually in the class.</p>

CC BY-SA 4.0
2021-03-18T21:43:09.117Z
2021-03-18T21:43:09.117Z
usul
<p>I have read the no free lunch theorem(NFLT) section 5.1 of <a href="https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/copy.html" rel="nofollow noreferrer">Understanding machine learning by Shai Shalev-Shwartz</a>. There is also this Corollary 4.6 which states any finite hypothesis class is PAC learnable.</p>
<p>The book applies the NFLT to the hypothesis class that includes all the functions of an infinite domain to prove they are not PAC learnable. (Corollary 5.2).</p>
<p>I want to investigate why applying the same proof (using NFLT) for the case of finite hypothesis classes fails but have a hard time doing that.</p>
<p>In particular given an infinite domain <span class="math-container">$\chi$</span> I need to show <span class="math-container">$\exists (\epsilon , \delta) $</span> such that for all <span class="math-container">$m \in \mathbb{N}$</span> the probability of <span class="math-container">$L_{D}(h) \ge min_{h'\in H} L_{D}(h') + \epsilon$</span> is more than <span class="math-container">$\delta$</span> (assumning <span class="math-container">$h$</span> is the output of a learning algorithm). my guess is that the hypothesis <span class="math-container">$f$</span> (mentioned in the NFLT) with <span class="math-container">$L_{D}(f) = 0$</span> doesn't necessarily fall into the hypothesis class since the number of these function grows by the number of sample but the cardinality of the hypothesis class is constant. But I'm not sure how accurate this is.</p>

<machine-learning><pac-learning>
No free lunch theorem and finite hypothesis classes
KFkf
# No free lunch theorem and finite hypothesis classes

(Asked by: username_0 on 2021-03-16)

I have read the no free lunch theorem(NFLT) section 5.1 of [Understanding machine learning by Shai Shalev-Shwartz](https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/copy.html). There is also this Corollary 4.6 which states any finite hypothesis class is PAC learnable.

The book applies the NFLT to the hypothesis class that includes all the functions of an infinite domain to prove they are not PAC learnable. (Corollary 5.2).

I want to investigate why applying the same proof (using NFLT) for the case of finite hypothesis classes fails but have a hard time doing that.

In particular given an infinite domain $\chi$ I need to show $\exists (\epsilon , \delta) $ such that for all $m \in \mathbb{N}$ the probability of $L\_{D}(h) \ge min\_{h'\in H} L\_{D}(h') + \epsilon$ is more than $\delta$ (assumning $h$ is the output of a learning algorithm). my guess is that the hypothesis $f$ (mentioned in the NFLT) with $L\_{D}(f) = 0$ doesn't necessarily fall into the hypothesis class since the number of these function grows by the number of sample but the cardinality of the hypothesis class is constant. But I'm not sure how accurate this is.

**Tags:** machine-learning, pac-learning


---

## 1 answers

### Answer by username_1 on 2021-03-18. Score: 0

Your guess is correct. The proof of No Free Lunch constructs a distribution over a large domain (comparable to $m$), and it considers a hypothesis class containing all functions on that domain (about $2^m$ of them). It then shows hardness of learning for that setting. So if we have an infinite domain and the corresponding infinite hypothesis class, then for every finite $m$, we get an impossibility result. So that infinite class is not PAC learnable.

But if we have a finite hypothesis class, then there will be some large enough $m$ where this construction won't work, since it would require constructing more hypotheses (about $2^m$ of them) than are actually in the class.


---

