PAC learnability of a concept class under non-atomic measures: a problem by Vidyasagar

In response to a 1997 problem of M. Vidyasagar, we state a necessary and sufficient condition for distribution-free PAC learnability of a concept class $\mathcal{C}$ under the family of all non-atomic (diffuse) measures on the domain $\mathrm{\Omega }$. Clearly, finiteness of the classical Vapnik-Chervonenkis dimension of $\mathcal{C}$ is a sufficient, but no longer necessary, condition. Besides, learnability of $\mathcal{C}$ under non-atomic measures does not imply the uniform Glivenko-Cantelli property with regard to non-atomic measures. Our learnability criterion is stated in terms of a combinatorial parameter $\text{VC}(\mathcal{C}\mathrm{m}\mathrm{o}\mathrm{d}{\omega }_1)$ which we call the VC dimension of $\mathcal{C}$ modulo countable sets. The new parameter is obtained by thickening up'' single points in the definition of VC dimension to uncountable clusters’'. Equivalently, $\text{VC}(\mathcal{C}\text{modd}{\omega }_1)\le d$ if and only if every countable subclass of $\mathcal{C}$ has VC dimension $\le d$ outside a countable subset of $\mathrm{\Omega }$. The new parameter can be also expressed as the classical VC dimension of $\mathcal{C}$ calculated on a suitable subset of a compactification of $\mathrm{\Omega }$. We do not make any measurability assumptions on $\mathcal{C}$, assuming instead the validity of Martin’s Axiom (MA).