<p>I don't understand exactly your question, but I'll answer it from the two possible misunderstandings I can see.
The first confusion comes from your definition of the function <span class="math-container">$m_\mathcal{H} : (0, 1)^2 \to \mathbb{N}$</span>, in your case the function is exactly <span class="math-container">$m_\mathcal{H} (\epsilon, \delta) = \left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil$</span>.</p>
<p>The theorem gives you a lower bound to guarantee PAC-learnability this lower bound depends on the precision, the accuracy, and the &quot;complexity&quot; of your hypothesis class which in this case is measured by its size. This can be seen as a necessary condition for PAC learnability. On the other hand, The upper bound gives you a sufficient condition for PAC learnability.</p>
<p>If you're asking whether there is a tighter lower bound, the answer is yes, but needs to be expressed using other information complexities of the hypothesis class instead of the the size. VC dimension is an example of this information complexity.</p>

CC BY-SA 4.0
2023-11-10T03:56:18.713Z
Thanks. If in my case, $ m_\mathcal{H}(\epsilon, \delta) = \left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil$. Then can you tell me a case where , $ m_\mathcal{H}(\epsilon, \delta) \lt \left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil$ and still PAC learning works ? My confusion arises from being unable to see such a case.
Sathishkumar Thirumalai
CC BY-SA 4.0
2023-11-09T12:57:12.607Z
2023-11-09T13:07:36.793Z
2023-11-09T13:07:36.793Z
Saginus
<p>I have been studying from the book &quot;Understanding Machine Learning - From Theory to Algorithms&quot; by Shai Shalev-Shwartz and Shai Ben-David
I am struck at corollary 3.2 which states that</p>
<p><em>Every finite hypothesis class is PAC learnable with sample complexity</em></p>
<p><span class="math-container">$ m_\mathcal{H} (\epsilon, \delta) \le \left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil $</span></p>
<p>where <span class="math-container">$  \mathcal{H}  $</span> is the hypothesis class and <span class="math-container">$ \epsilon &gt; 0 $</span> and <span class="math-container">$ \delta  \in (0,1) $</span></p>
<p>and <span class="math-container">$ m_\mathcal{H} : (0, 1)^2 \to \mathbb{N}  $</span></p>
<p>My doubt is regarding the <span class="math-container">$ \le $</span> in the above equation.</p>
<p>I have understood PAC learnability as</p>
<p>&quot;If we choose a sample set <span class="math-container">$ S $</span>  with  <span class="math-container">$m$</span> samples such that <span class="math-container">$ m \ge m_\mathcal{H} (\epsilon, \delta) $</span>, then  <span class="math-container">$ \mathcal{H}  $</span>  is learnable with confidence <span class="math-container">$ 1- \delta $</span> and accuracy <span class="math-container">$ \epsilon $</span>  &quot;</p>
<p>I have understood the sample complexity as</p>
<p>&quot; The minimal function <span class="math-container">$  m_\mathcal{H} (\epsilon, \delta) $</span> that gives the smallest integer for any <span class="math-container">$ \epsilon $</span> and <span class="math-container">$ \delta$</span> such that PAC learning is guaranteed &quot;</p>
<p>Further, in the same book corollary 2.3 states</p>
<p>for PAC learnability,</p>
<p><span class="math-container">$ m  \ge       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}      $</span></p>
<p>From the above, my understanding of PAC learning is choose a  <span class="math-container">$\mathcal{m}$</span> that is bigger than <span class="math-container">$ \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon} $</span> and also choose a  <span class="math-container">$\mathcal{m}$</span> that is bigger than <span class="math-container">$ m_\mathcal{H} (\epsilon, \delta) $</span>.</p>
<p>But, how does the relationship in Corollary 3.2  arrived?</p>
<p>What fails if <span class="math-container">$ m_\mathcal{H} (\epsilon, \delta) \ge \left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil $</span> ?</p>

CC BY-SA 4.0
2023-11-09T12:03:49.713Z
$m_{\mathcal{H}}$ is defined to be the minimal $m$ that works. Since $m = \lceil \frac{\log(\frac{|\mathcal{H}|}{\delta})}{\epsilon}\rceil$ works, we know $m_{\mathcal{H}} \le \lceil \frac{\log(\frac{|\mathcal{H}|}{\delta})}{\epsilon}\rceil$.
mathworker21
CC BY-SA 4.0
2023-11-09T12:08:46.603Z
Thanks. Does that mean there are "other" m's less than $\left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil$ that will also work? i know any m greater than $\left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil$ works.
Sathishkumar Thirumalai
CC BY-SA 4.0
2023-11-09T14:07:23.930Z
The question you're asking is the lower bound for the sample complexity of PAC learning. The textbook you mentioned discusses this question.
mathworker21
<machine-learning><pac-learning><sample-complexity>
Unable to understand the Sample complexity of PAC learning
Sathishkumar Thirumalai
# Unable to understand the Sample complexity of PAC learning

(Asked by: username_0 on 2023-11-09)

I have been studying from the book "Understanding Machine Learning - From Theory to Algorithms" by Shai Shalev-Shwartz and Shai Ben-David
I am struck at corollary 3.2 which states that

*Every finite hypothesis class is PAC learnable with sample complexity*

$ m\_\mathcal{H} (\epsilon, \delta) \le \left \lceil \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon} \right \rceil $

where $ \mathcal{H} $ is the hypothesis class and $ \epsilon > 0 $ and $ \delta \in (0,1) $

and $ m\_\mathcal{H} : (0, 1)^2 \to \mathbb{N} $

My doubt is regarding the $ \le $ in the above equation.

I have understood PAC learnability as

"If we choose a sample set $ S $ with $m$ samples such that $ m \ge m\_\mathcal{H} (\epsilon, \delta) $, then $ \mathcal{H} $ is learnable with confidence $ 1- \delta $ and accuracy $ \epsilon $ "

I have understood the sample complexity as

" The minimal function $ m\_\mathcal{H} (\epsilon, \delta) $ that gives the smallest integer for any $ \epsilon $ and $ \delta$ such that PAC learning is guaranteed "

Further, in the same book corollary 2.3 states

for PAC learnability,

$ m \ge \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon} $

From the above, my understanding of PAC learning is choose a $\mathcal{m}$ that is bigger than $ \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon} $ and also choose a $\mathcal{m}$ that is bigger than $ m\_\mathcal{H} (\epsilon, \delta) $.

But, how does the relationship in Corollary 3.2 arrived?

What fails if $ m\_\mathcal{H} (\epsilon, \delta) \ge \left \lceil \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon} \right \rceil $ ?

**Tags:** machine-learning, pac-learning, sample-complexity
> **Comments:**
> **username_1**: $m_{\mathcal{H}}$ is defined to be the minimal $m$ that works. Since $m = \lceil \frac{\log(\frac{|\mathcal{H}|}{\delta})}{\epsilon}\rceil$ works, we know $m_{\mathcal{H}} \le \lceil \frac{\log(\frac{|\mathcal{H}|}{\delta})}{\epsilon}\rceil$.  
> **username_0**: Thanks. Does that mean there are "other" m's less than $\left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil$ that will also work? i know any m greater than $\left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil$ works.  
> **username_1**: The question you're asking is the lower bound for the sample complexity of PAC learning. The textbook you mentioned discusses this question.  

---

## 1 answers

### Answer by username_2 on 2023-11-09. Score: 0 | Accepted answer

I don't understand exactly your question, but I'll answer it from the two possible misunderstandings I can see.
The first confusion comes from your definition of the function $m\_\mathcal{H} : (0, 1)^2 \to \mathbb{N}$, in your case the function is exactly $m\_\mathcal{H} (\epsilon, \delta) = \left \lceil \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon} \right \rceil$.

The theorem gives you a lower bound to guarantee PAC-learnability this lower bound depends on the precision, the accuracy, and the "complexity" of your hypothesis class which in this case is measured by its size. This can be seen as a necessary condition for PAC learnability. On the other hand, The upper bound gives you a sufficient condition for PAC learnability.

If you're asking whether there is a tighter lower bound, the answer is yes, but needs to be expressed using other information complexities of the hypothesis class instead of the the size. VC dimension is an example of this information complexity.

> **Comments:**
> **username_0**: Thanks. If in my case, $ m_\mathcal{H}(\epsilon, \delta) = \left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil$. Then can you tell me a case where , $ m_\mathcal{H}(\epsilon, \delta) \lt \left \lceil       \frac{ \log{\left(\frac{|\mathcal{H}|}{\delta}\right)} }{\epsilon}     \right \rceil$ and still PAC learning works ? My confusion arises from being unable to see such a case.  

---

