A learning problem whose consistency is equivalent to the non-existence of real-valued measurable cardinals
This work addresses a foundational theoretical problem in machine learning by linking learning consistency to set-theoretic axioms, which is incremental as it builds on prior intuitive examples.
The paper tackles the problem of determining when the k-nearest neighbor learning rule is universally consistent in metric spaces, showing that this occurs if and only if the density of the space is less than every real-measurable cardinal and separable subspaces are consistent, which is equivalent to the non-existence of real-valued measurable cardinals.
We show that the $k$-nearest neighbour learning rule is universally consistent in a metric space $X$ if and only if it is universally consistent in every separable subspace of $X$ and the density of $X$ is less than every real-measurable cardinal. In particular, the $k$-NN classifier is universally consistent in every metric space whose separable subspaces are sigma-finite dimensional in the sense of Nagata and Preiss if and only if there are no real-valued measurable cardinals. The latter assumption is relatively consistent with ZFC, however the consistency of the existence of such cardinals cannot be proved within ZFC. Our results were inspired by an example sketched by Cérou and Guyader in 2006 at an intuitive level of rigour.