This note will introduce the ideas presented by Vapnik, presented in (Shalev-Shwartz & Ben-David 2014) chapter 6. Briefly this says that infinite-size classes are indeed learnable.

This set of note is still a work in progress. But it’s very important for statistical learning theory.

We have that if $\lvert \mathcal{H} \rvert < \infty \implies vc(\mathcal{H} \rvert) \leq \log_{2} \lvert \mathcal{H}$ Example: if $\mathcal{H}$ is the set of linear classifiers on $\mathbb{R}^{d}$ then we have that the dimension is $d + 1$.

if $vc(\mathcal{H}) < \infty \implies E_{m}(\mathcal{H}) = \sqrt{ vc(\mathcal{H} / m) }$ which means every finite hypothesis set is learnable. $m$ is the size of our training set.

Even if $vc(\mathcal{H}) = \infty$ there exists a class $C > 0$ that makes it to be learnable. But I did not understood the details.

References

[1] Shalev-Shwartz & Ben-David “Understanding Machine Learning: From Theory to Algorithms” Cambridge University Press 2014