Answers.Body: <p>There is no contradiction between PAC learning and the no-free-lunch theorem as commented in other answers.</p>
  <p><strong>But there is indeed a contradiction between the no-free-lunch theorem and its layman's explanation:</strong></p>
  <ul>
  <li>for infinite <span class="math-container">$\mathcal{X}$</span>, whenever <span class="math-container">$\mathcal A$</span> is fixed, there is a distribution on which it fails to learn.</li>
  </ul>
  <p><strong>This is not true!</strong></p>
  <p>Indeed, if <span class="math-container">$\mathcal X$</span> is countable and <span class="math-container">$\mathcal A$</span> is an algorithm that simply memorizes what it has seen and answers <span class="math-container">$0$</span> for unseen samples, then it can be shown that the true error of <span class="math-container">$\mathcal A$</span> converges to <span class="math-container">$0$</span>, so <span class="math-container">$\mathcal A$</span> effectively learns. (See page 95)</p>
  <p>For uncountable <span class="math-container">$\mathcal X$</span>, the layman's explanation is correct. In that case, the theorem looks rather obvious, because finite samples provide no information about the behavior of the true mapping <span class="math-container">$f$</span>, except at a null set.</p>
  <p>I personally dislike that part of the book (page 61), because immediately before the no-free-lunch theorem, they say literally &quot;<em>no learner can succeed on all learning task, as formalized in the following theorem:</em>&quot;, but they leave the distribution <span class="math-container">$\mathcal D$</span> as dependent on <span class="math-container">$m$</span> in the theorem statement, which disrupts all the previous definitions of learnability and makes the introductory phrase (the layman's terms) misleading.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-01T07:52:37.167Z
Answers.LastActivityDate: 2022-02-01T07:52:37.167Z
Answers.UserDisplayName: Carlos Pinzón
Answers.Body: <p>PAC-learning is a <strong>definition</strong> and imposes a <strong>condition</strong> (<em>&quot;if, for all distribution, and other conditions are met then...&quot;</em>) that, if met, then the class is PAC-learnable.</p>
  <p>NFL Theorem is a <strong>result</strong>: There is always a distribution that makes the learner not learn.</p>
  <p><strong>The main observation:</strong> the statement of the NFL Theorem does not specify which class <span class="math-container">$\mathcal{H}$</span> the learner is using, so it manages to prove that the learner fail miserably.</p>
  <p><strong>Conclusion</strong>: if <span class="math-container">$\mathcal{H}$</span> is not restricted in some way, then the NFL theorem is valid. However, if we restrict <span class="math-container">$\mathcal{H}$</span>, then - maybe - the conditions of the PAC-learning definition will be met.</p>
  <p>For example, some successful learners (as presented in the &quot;<em>Understanding Machine Learning</em>&quot; book, right after the NFL statement):</p>
  <ul>
  <li>ERM with <span class="math-container">$\mathcal{H} = \{f\}$</span></li>
  <li>ERM with <span class="math-container">$\mathcal{H}$</span> finite that contains <span class="math-container">$f$</span> and whose size satisfies <span class="math-container">$m \ge 8 \log(7|\mathcal{H}|/6)$</span> (Corollary 2.3)</li>
  </ul>
  <p>These learners respect item (1) of the NFL theorem statement (&quot;<em>exists <span class="math-container">$f: \mathcal{X} \rightarrow \{0,1\}$</span> with <span class="math-container">$L_{\mathcal{D}}(f)=0$</span></em>&quot;) because they restrict <span class="math-container">$\mathcal{H}$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-09T15:38:32.610Z
Answers.LastActivityDate: 2024-02-09T16:02:41.130Z
Answers.LastEditDate: 2024-02-09T16:02:41.130Z
Answers.UserDisplayName: avignatti
Answers.Body: <p>There is no contradiction. 
  First, agnostic PAC learnable doesn't mean that the there is a good hypothesis in the hypothesis class; it just means that there is an algorithm that can probably approximately do as well as the best hypothesis in the hypothesis class.</p>
  
  <p>Also, these NFL theorems have specific mathematical statements, and hypothesis classes for which they apply are often not the same as the hypothesis class for which PAC-learnability holds. For example, in <em>Understanding Machine Learning</em>  by Shalev-Shwartz and Ben-David, a hypothesis class is agnostic PAC learnable if and only if has finite VC dimension (Theorem 6.7). Here, the algorithm is ERM.
  On the other hand, the application of the specific version of NFL that this book uses has Corollary 5.2, that the hypothesis class of all classifiers is not PAC learnable, and note that this hypothesis class has infinite VC dimension, so the Fundamental Theorem of PAC learning does not apply.</p>
  
  <p>The main takeaway is that in order to learn, we need some sort of inductive bias (prior information). This can be seen in the form of measuring the complexity of the hypothesis class or using other tools in learning theory. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-05T03:01:29.140Z
Answers.LastActivityDate: 2020-02-05T03:01:29.140Z
Answers.UserDisplayName: Anon
Body: <p>I am reading the Understanding Machine Learning book by Shalev-Shwartz and Ben-David and based on the definitions of PAC learnability and No Free Lunch Theorem, and my understanding of them it seems like they contradict themselves. I know this is not the case and I am wrong, but I just don't know what I am missing here.</p>
  
  <p>So, a hypothesis class is (agnostic) PAC learnable if there exists a learner A and a function <span class="math-container">$m_{H}$</span> s.t. for every <span class="math-container">$\epsilon,\delta \in (0,1)$</span> and <strong>for every distribution <span class="math-container">$D$</span> over <span class="math-container">$X \times Y$</span></strong>, if <span class="math-container">$m \geq m_{H}$</span> the learner can return a hypothesis <span class="math-container">$h$</span>, with a probability of at least <span class="math-container">$1 - \delta$</span>
  <span class="math-container">$$ L_{D}(h) \leq min_{h'\in H} L_{D}(h') + \epsilon $$</span></p>
  
  <p>But, in layman's terms, the NFL theorem states that for prediction tasks, for every learner there <strong>exists a distribution</strong> on which the learner fails.  </p>
  
  <p>There needs to exists a learner that is successful (defined above) for every distribution <span class="math-container">$D$</span> over <span class="math-container">$X \times Y$</span> for a hypothesis to be PAC learnable, but according to NFL there exists a distribution for which the learner will fail, aren't these theorems contradicting themselves?</p>
  
  <p>What am I missing or misinterpreting here?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-02-02T20:20:02.980Z
Comments.Text: PAC learnability is about learning **approximately** and **probably**. In fact, PAC stands for _probably approximately correct_. It doesn't (necessarily) guarantee that you will learn the correct hypothesis with probability 1. I am not familiar with the details of the NFL theorem(s), so I cannot say more now, but a proper answer to your question probably includes this information I've just mentioned.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-02-02T20:34:26.367Z
Comments.Text: I do take that into consideration. The NFL theorem also defines the failure of a learner in terms of a probability $(1- \delta)$ and an error threshold $\epsilon$
Comments.UserDisplayName: Jonathan Azpur
Tags: <machine-learning><comparison><computational-learning-theory><pac-learning><no-free-lunch-theorems>
Title: Are PAC learnability and the No Free Lunch theorem contradictory?
UserDisplayName: Jonathan Azpur
ThreadText: # Are PAC learnability and the No Free Lunch theorem contradictory?
  
  (Asked by: username_0 on 2020-02-02)
  
  I am reading the Understanding Machine Learning book by Shalev-Shwartz and Ben-David and based on the definitions of PAC learnability and No Free Lunch Theorem, and my understanding of them it seems like they contradict themselves. I know this is not the case and I am wrong, but I just don't know what I am missing here.
  
  So, a hypothesis class is (agnostic) PAC learnable if there exists a learner A and a function $m\_{H}$ s.t. for every $\epsilon,\delta \in (0,1)$ and **for every distribution $D$ over $X \times Y$**, if $m \geq m\_{H}$ the learner can return a hypothesis $h$, with a probability of at least $1 - \delta$
  $$ L\_{D}(h) \leq min\_{h'\in H} L\_{D}(h') + \epsilon $$
  
  But, in layman's terms, the NFL theorem states that for prediction tasks, for every learner there **exists a distribution** on which the learner fails.
  
  There needs to exists a learner that is successful (defined above) for every distribution $D$ over $X \times Y$ for a hypothesis to be PAC learnable, but according to NFL there exists a distribution for which the learner will fail, aren't these theorems contradicting themselves?
  
  What am I missing or misinterpreting here?
  
  **Tags:** machine-learning, comparison, computational-learning-theory, pac-learning, no-free-lunch-theorems
  
  > **Comments:**
  > **username_1**: PAC learnability is about learning **approximately** and **probably**. In fact, PAC stands for _probably approximately correct_. It doesn't (necessarily) guarantee that you will learn the correct hypothesis with probability 1. I am not familiar with the details of the NFL theorem(s), so I cannot say more now, but a proper answer to your question probably includes this information I've just mentioned.  
  > **username_0**: I do take that into consideration. The NFL theorem also defines the failure of a learner in terms of a probability $(1- \delta)$ and an error threshold $\epsilon$  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_4 on 2020-02-05. Score: 6 | Accepted answer
  
  There is no contradiction.
  First, agnostic PAC learnable doesn't mean that the there is a good hypothesis in the hypothesis class; it just means that there is an algorithm that can probably approximately do as well as the best hypothesis in the hypothesis class.
  
  Also, these NFL theorems have specific mathematical statements, and hypothesis classes for which they apply are often not the same as the hypothesis class for which PAC-learnability holds. For example, in *Understanding Machine Learning* by Shalev-Shwartz and Ben-David, a hypothesis class is agnostic PAC learnable if and only if has finite VC dimension (Theorem 6.7). Here, the algorithm is ERM.
  On the other hand, the application of the specific version of NFL that this book uses has Corollary 5.2, that the hypothesis class of all classifiers is not PAC learnable, and note that this hypothesis class has infinite VC dimension, so the Fundamental Theorem of PAC learning does not apply.
  
  The main takeaway is that in order to learn, we need some sort of inductive bias (prior information). This can be seen in the form of measuring the complexity of the hypothesis class or using other tools in learning theory.
  
  
  ---
  
  ### Answer by username_2 on 2022-02-01. Score: 0
  
  There is no contradiction between PAC learning and the no-free-lunch theorem as commented in other answers.
  
  **But there is indeed a contradiction between the no-free-lunch theorem and its layman's explanation:**
  
  * for infinite $\mathcal{X}$, whenever $\mathcal A$ is fixed, there is a distribution on which it fails to learn.
  
  **This is not true!**
  
  Indeed, if $\mathcal X$ is countable and $\mathcal A$ is an algorithm that simply memorizes what it has seen and answers $0$ for unseen samples, then it can be shown that the true error of $\mathcal A$ converges to $0$, so $\mathcal A$ effectively learns. (See page 95)
  
  For uncountable $\mathcal X$, the layman's explanation is correct. In that case, the theorem looks rather obvious, because finite samples provide no information about the behavior of the true mapping $f$, except at a null set.
  
  I personally dislike that part of the book (page 61), because immediately before the no-free-lunch theorem, they say literally "*no learner can succeed on all learning task, as formalized in the following theorem:*", but they leave the distribution $\mathcal D$ as dependent on $m$ in the theorem statement, which disrupts all the previous definitions of learnability and makes the introductory phrase (the layman's terms) misleading.
  
  
  ---
  
  ### Answer by username_3 on 2024-02-09. Score: 0
  
  PAC-learning is a **definition** and imposes a **condition** (*"if, for all distribution, and other conditions are met then..."*) that, if met, then the class is PAC-learnable.
  
  NFL Theorem is a **result**: There is always a distribution that makes the learner not learn.
  
  **The main observation:** the statement of the NFL Theorem does not specify which class $\mathcal{H}$ the learner is using, so it manages to prove that the learner fail miserably.
  
  **Conclusion**: if $\mathcal{H}$ is not restricted in some way, then the NFL theorem is valid. However, if we restrict $\mathcal{H}$, then - maybe - the conditions of the PAC-learning definition will be met.
  
  For example, some successful learners (as presented in the "*Understanding Machine Learning*" book, right after the NFL statement):
  
  * ERM with $\mathcal{H} = \{f\}$
  * ERM with $\mathcal{H}$ finite that contains $f$ and whose size satisfies $m \ge 8 \log(7|\mathcal{H}|/6)$ (Corollary 2.3)
  
  These learners respect item (1) of the NFL theorem statement ("*exists $f: \mathcal{X} \rightarrow \{0,1\}$ with $L\_{\mathcal{D}}(f)=0$*") because they restrict $\mathcal{H}$.
  
  
  ---
  
  