I am new to Machine Learning theory and some of the topics are not very intuitive to me. I don't quite understand how the sample complexity in PAC theorem depends only on the concept class.

As we see in the definition there exists an algorithm...:

Definition 1 (PAC-learnable concept class)
A concept class is PAC-learnable if there exists an algorithm $\mathcal{A}$ and a polynomial function $poly(., ., ., .)$ if for every $\epsilon > 0$, $\delta> 0$, for every distribution $\mathcal{D}$ on $\mathcal{X}$ and every concept $c \in \mathcal{C}$, the following holds for every $m \geq poly(1/\epsilon, 1/\delta, n, size(c))$: $$P_{D−S^m}[R(h_S) \leq \epsilon] \geq 1 − \delta$$

Is there any theorem or way to prove/discuss that a specific algorithm is a PAC-learner for a chosen concept class?
Let's say I have two different algorithms how can I argue/show one is a PAC-learner and the other not? What features make an algorithm a learner?
One could show the sample complexity of an algorithm by the number of queries to the oracle and compare it with the bound from PAC theorem, but this alone doesn't make an algorithm a learner, or does it?

An answer or any reference/paper is appreciated.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.