PAC learnable bound with VC-dimension

machine-learning

Statement

Lemma

For a learner with a hypothesis space $H$ with VC dimension $VC(H)$ then by drawing

$$m \geq \frac{1}{\epsilon} \left (8 \ VC(H) \cdot \log_2(\frac{13}{\epsilon}) + 4 \log_2(\frac{2}{\delta}) \right)$$

i.i.d. samples for training data $T$ if there are any hypothesis consistent with $T$ then this will be a PAC learner with $\leq \epsilon$ accuracy with probability $1-\delta$.

Proof