# Universal Bayes consistency in metric spaces

arXiv: https://arxiv.org/abs/1906.09855 · HTML: https://mlsanity.com/paper/1906.09855/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2019.

## Built on by (most cited first, 30 of 33)

- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [Minimum Description Length and Generalization Guarantees for Representation Learning](https://mlsanity.com/paper/2402.03254/) (2024)
- [Survival Kernets: Scalable and Interpretable Deep Kernel Survival Analysis with an Accuracy Guarantee](https://mlsanity.com/paper/2206.10477/) (2022)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [Universal Online Learning with Bounded Loss: Reduction to Binary Classification](https://mlsanity.com/paper/2112.14638/) (2021)
- [Universal Online Learning with Unbounded Losses: Memory Is All You Need](https://mlsanity.com/paper/2201.08903/) (2022)
- [A Theory of Interpretable Approximations](https://mlsanity.com/paper/2406.10529/) (2024)
- [Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?](https://mlsanity.com/paper/2107.09542/) (2021)
- [Universally Consistent Online Learning with Arbitrarily Dependent Responses](https://mlsanity.com/paper/2203.06046/) (2022)
- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Universal Regression with Adversarial Responses](https://mlsanity.com/paper/2203.05067/) (2022)
- [From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability](https://mlsanity.com/paper/2106.01382/) (2021)
- [Metric-valued regression](https://mlsanity.com/paper/2202.03045/) (2022)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)
- [Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priors](https://mlsanity.com/paper/2502.15540/) (2025)
- [End-to-End Deep Learning for Predicting Metric Space-Valued Outputs](https://mlsanity.com/paper/2509.23544/) (2025)
- [On Error and Compression Rates for Prototype Rules](https://mlsanity.com/paper/2206.08014/) (2022)
- [Recursive Estimation of Conditional Kernel Mean Embeddings](https://mlsanity.com/paper/2302.05955/) (2023)
- [A Theory of Optimistically Universal Online Learnability for General Concept Classes](https://mlsanity.com/paper/2501.08551/) (2025)
- [Multiview Representation Learning via Distributed Joint Latent Space Structuring](https://mlsanity.com/paper/2504.18455/) (2025)
- [Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory](https://mlsanity.com/paper/2105.09788/) (2021)
- [Differentially-Private Bayes Consistency](https://mlsanity.com/paper/2212.04216/) (2022)
- [Weighted Distance Nearest Neighbor Condensing](https://mlsanity.com/paper/2310.15951/) (2023)
- [When Is Inductive Inference Possible?](https://mlsanity.com/paper/2312.00170/) (2023)
- [Error Exponent in Agnostic PAC Learning](https://mlsanity.com/paper/2405.00792/) (2024)
- [Universal consistency of the k-NN rule in metric spaces and Nagata dimension. III](https://mlsanity.com/paper/2512.17058/) (2025)
- [Metric space valued Fr'echet regression](https://mlsanity.com/paper/2602.05225/) (2026)
- [Random-Effects Algorithm for Random Objects in Metric Spaces](https://mlsanity.com/paper/2605.02693/) (2026)
- [Realizable Bayes-Consistency for General Metric Losses](https://mlsanity.com/paper/2605.03823/) (2026)

## Abstract (arXiv)

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.