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

2025/12/18 by Pestov, Vladimir G.
#54F45 #62H30 #FOS: Computer and information sciences #I.2.6 #I.5.1 #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2512.17058

Abstract

We prove the last remaining implication allowing to claim the equivalence of the following conditions for a complete separable metric space X: (1) The k-nearest neighbour classifier is (weakly) 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 Nagata. The equivalence (2)\iff(3) was announced by Preiss (1983), while a detailed proof of the implication (3)⇒(2) has appeared in Assouad and Quentin de Gromard (2006). The implication (2)⇒(1) was established by Cérou and Guyader (2006). We prove the implication (1)⇒(3). The result was conjectured in the first article in the series (Collins, Kumari, Pestov 2020), and here we also correct a wrong claim made in the second article (Kumari and Pestov 2024).

Citations

• Topics in Random Matrices and Statistical Machine Learning
• A Survey on Metric Learning for Feature Vectors and Structured Data
• Consistent Nonparametric Regression

Related

• Differentiation of measures in metric spaces
• The Globalization Theorem for CD(K,N) on locally finite Spaces
• On asymptotic dimension and a property of Nagata
• Besicovitch and doubling type properties in metric spaces
• Borel regularity is equivalent to Lusin's theorem and the existence of Borel representatives