Unable to understand the Sample complexity of PAC learning

Question

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

Answer 1

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.