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 $|\mathcal{H}|<\infty ⟹vc(\mathcal{H}|)\le {\log }_2|\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 ⟹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