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

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.