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