Answers.Body: <p>Definitely, you can find the proof in different resources (for example, in <a href="http://karlstratos.com/notes/pac.pdf" rel="nofollow noreferrer">these notes</a> or in the paper that originally proposed PAC learnability, <a href="http://web.mit.edu/6.435/www/Valiant84.pdf" rel="nofollow noreferrer">A Theory of the Learnable</a>). However, the intuition behind your question is when the size of the hypothesis increases, if you do not change anything, you can't see more part of the space. Hence, the estimation error will increase. Moreover, when you increase the number of samples, you have more chance to see more part of the hypothesis space, hence, the estimation error decrease.</p>
  <p>Also, you can see some lemma about the relation of the PAC learnability and other similar concepts in the Wikipedia article <a href="https://en.wikipedia.org/wiki/Probably_approximately_correct_learning" rel="nofollow noreferrer">Probably approximately correct learning</a>:</p>
  <blockquote>
  <p>Under some regularity conditions these three conditions are equivalent:</p>
  <ol>
  <li>The concept class <span class="math-container">$C$</span> is PAC learnable.</li>
  <li>The VC dimension of <span class="math-container">$C$</span> is finite.</li>
  <li><span class="math-container">$C$</span> is a uniform Glivenko-Cantelli class.</li>
  </ol>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-16T11:45:56.953Z
Answers.Text: Thanks. But it seems that this paper doesn't provide the proof but the sample complexity. For a finite class H, $m_H(\epsilon,\delta)\le\lceil\frac{log(|H|/\delta)}{\epsilon}\rceil$. But how could we draw the conclusion that we discussed?
Answers.UserDisplayName: Ben
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-16T12:23:54.677Z
Answers.Text: @ChenglinBen this part is the definition of the PAC learnability and a definition does not need any proof.
Answers.UserDisplayName: OmG
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-16T12:26:40.817Z
Answers.Text: I know that. I mean that maybe our discussion about that estimation error increase (logarithmically) with || and decrease with  in PAC learning can be inspired by this. I'm not intended to prove the definition of PAC learnability.
Answers.UserDisplayName: Ben
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-16T12:28:38.237Z
Answers.Text: @ChenglinBen may be the last part of post (it is updated) could help. Indeed, the relation of the PAC learnability with other similar concepts such as VC dimension could help to know better the concept. The proof of the equivalency of these concepts could help to prove what you want.
Answers.UserDisplayName: OmG
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-16T12:32:53.413Z
Answers.Text: First, thank you very much. But I'm sorry that maybe I didn't state my question clearly. What I would like to do is prove that estimation error $\epsilon_{est}$ increase (logarithmically) with || and decrease with . Because the book I mentioned initially stated this conclusion toughly, I would like to figure out the rigorous proof. Hope you can help me out.
Answers.UserDisplayName: Ben
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-16T11:25:55.493Z
Answers.LastActivityDate: 2019-09-17T17:04:52.413Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: OmG
Body: <p>Why does estimation error increase with <span class="math-container">$|H|$</span> and decrease with <span class="math-container">$m$</span> in PAC learning?</p>
  
  <p>I came across <a href="https://i.sstatic.net/JLnLi.png" rel="nofollow noreferrer">this statement</a> in the section 5.2 of the book <a href="https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf" rel="nofollow noreferrer">"understanding machine learning: from theory to algorithms"</a>. You just search "<strong>increases (logarithmically)</strong>" in your browser and then you can find the sentence.</p>
  
  <p>I just can't understand the statement. And there is no proof in the book either. What I would like to do is prove that estimation error <span class="math-container">$\epsilon_{est}$</span> increase (logarithmically) with || and decrease with . Hope you can help me out. A rigorous proof can't be better!</p>
  
Tags: <machine-learning><proofs><computational-learning-theory><pac-learning>
Title: Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?
UserDisplayName: Ben
ThreadText: # Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?
  
  (Asked by: username_0 on 2019-09-16)
  
  Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?
  
  I came across [this statement](https://i.sstatic.net/JLnLi.png) in the section 5.2 of the book ["understanding machine learning: from theory to algorithms"](https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf). You just search "**increases (logarithmically)**" in your browser and then you can find the sentence.
  
  I just can't understand the statement. And there is no proof in the book either. What I would like to do is prove that estimation error $\epsilon\_{est}$ increase (logarithmically) with || and decrease with . Hope you can help me out. A rigorous proof can't be better!
  
  **Tags:** machine-learning, proofs, computational-learning-theory, pac-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-09-16. Score: 3
  
  Definitely, you can find the proof in different resources (for example, in [these notes](http://karlstratos.com/notes/pac.pdf) or in the paper that originally proposed PAC learnability, [A Theory of the Learnable](http://web.mit.edu/6.435/www/Valiant84.pdf)). However, the intuition behind your question is when the size of the hypothesis increases, if you do not change anything, you can't see more part of the space. Hence, the estimation error will increase. Moreover, when you increase the number of samples, you have more chance to see more part of the hypothesis space, hence, the estimation error decrease.
  
  Also, you can see some lemma about the relation of the PAC learnability and other similar concepts in the Wikipedia article [Probably approximately correct learning](https://en.wikipedia.org/wiki/Probably_approximately_correct_learning):
  
  > Under some regularity conditions these three conditions are equivalent:
  >
  > 1. The concept class $C$ is PAC learnable.
  > 2. The VC dimension of $C$ is finite.
  > 3. $C$ is a uniform Glivenko-Cantelli class.
  
  > **Comments:**
  > **username_0**: Thanks. But it seems that this paper doesn't provide the proof but the sample complexity. For a finite class H, $m_H(\epsilon,\delta)\le\lceil\frac{log(|H|/\delta)}{\epsilon}\rceil$. But how could we draw the conclusion that we discussed?  
  > **username_1**: @ChenglinBen this part is the definition of the PAC learnability and a definition does not need any proof.  
  > **username_0**: I know that. I mean that maybe our discussion about that estimation error increase (logarithmically) with || and decrease with  in PAC learning can be inspired by this. I'm not intended to prove the definition of PAC learnability.  
  > **username_1**: @ChenglinBen may be the last part of post (it is updated) could help. Indeed, the relation of the PAC learnability with other similar concepts such as VC dimension could help to know better the concept. The proof of the equivalency of these concepts could help to prove what you want.  
  > **username_0**: First, thank you very much. But I'm sorry that maybe I didn't state my question clearly. What I would like to do is prove that estimation error $\epsilon_{est}$ increase (logarithmically) with || and decrease with . Because the book I mentioned initially stated this conclusion toughly, I would like to figure out the rigorous proof. Hope you can help me out.  
  
  ---
  
  