Universal Bayes consistency in metric spaces
This work addresses a foundational problem in machine learning theory by providing a complete characterization of Bayes consistency in metric spaces, which is incremental in extending prior algorithms but foundational in its theoretical implications.
The authors tackled the problem of universal Bayes consistency in metric spaces by extending a 1-nearest-neighbor algorithm, proving it is universally strongly Bayes-consistent in all metric spaces that admit such a learner, making it the first 'optimistically universal' learner. They characterized the spaces where this is possible as 'essentially separable' and provided the first impossibility result for universal Bayes consistency.
We extend a recently proposed 1-nearest-neighbor based multiclass learning algorithm and prove that our modification is universally strongly Bayes-consistent in all metric spaces admitting any such learner, making it an "optimistically universal" Bayes-consistent learner. This is the first learning algorithm known to enjoy this property; by comparison, the $k$-NN classifier and its variants are not generally universally Bayes-consistent, except under additional structural assumptions, such as an inner product, a norm, finite dimension, or a Besicovitch-type property. The metric spaces in which universal Bayes consistency is possible are the "essentially separable" ones -- a notion that we define, which is more general than standard separability. The existence of metric spaces that are not essentially separable is widely believed to be independent of the ZFC axioms of set theory. We prove that essential separability exactly characterizes the existence of a universal Bayes-consistent learner for the given metric space. In particular, this yields the first impossibility result for universal Bayes consistency. Taken together, our results completely characterize strong and weak universal Bayes consistency in metric spaces.