# Unable to understand the Sample complexity of PAC learning

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$$ ?

• $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$. Nov 9 at 12:03
• 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. Nov 9 at 12:08
• The question you're asking is the lower bound for the sample complexity of PAC learning. The textbook you mentioned discusses this question. Nov 9 at 14:07

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$$.
• 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. Nov 10 at 3:56