# Universal consistency of the k-NN rule in metric spaces and Nagata dimension. III

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 34 references that are in the map.
- First posted on arXiv 18 Dec 2025.

## Builds on (most cited first, 5 of 5)

- [A Survey on Metric Learning for Feature Vectors and Structured Data](https://mlsanity.com/paper/1306.6709/) (2013)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Universal consistency of the k-NN rule in metric spaces and Nagata dimension](https://mlsanity.com/paper/2003.00894/) (2020)
- [Topics in Random Matrices and Statistical Machine Learning](https://mlsanity.com/paper/1807.09419/) (2018)
- [Universal consistency of the k-NN rule in metric spaces and Nagata dimension. II](https://mlsanity.com/paper/2305.17282/) (2023)

## Abstract (arXiv)

We establish the last missing link allowing to describe those complete separable metric spaces X in which the k nearest neighbour classifier is universally consistent, both in combinatorial terms of dimension theory and via a fundamental property of real analysis. The following are equivalent: (1) The k-nearest neighbour classifier is universally consistent in X, (2) The strong Lebesgue--Besicovitch differentiation property holds in X for every locally finite Borel measure, (3) X is sigma-finite dimensional in the sense of Jun-Iti Nagata. The equivalence (2)iff(3) was announced by Preiss (1983), while a detailed proof of the implication (3)Rightarrow(2) has only appeared in Assouad and Quentin de Gromard (2006). The implication (2)Rightarrow(1) was established by C'erou and Guyader (2006). We prove the implication (1)Rightarrow(3). We further show that the weak (instead of strong) Lebesgue--Besicovitch property is insufficient for the consistency of the k-NN rule, as witnessed, for example, by the Heisenberg group (here we correct a wrong claim made in the previous article (Kumari and Pestov 2024)). A bit counter-intuitively, there is a metric on the real line uniformly equivalent to the usual distance but under which the k-NN classifier fails. Finally, another equivalent condition that can be added to the above is the Cover--Hart property: (4) the error of the 1-nearest neighbour classifier is asymptotically at most twice as bad as the Bayes error.