Statement
Lemma
For a learner with a hypothesis space
with VC dimension then by drawing i.i.d. samples for training data if there are any hypothesis consistent with then this will be a PAC learner with accuracy with probability .
Lemma
For a learner with a hypothesis space
with VC dimension then by drawing i.i.d. samples for training data if there are any hypothesis consistent with then this will be a PAC learner with accuracy with probability .