Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension. III
By: Vladimir G. Pestov
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)$\Rightarrow$(2) has appeared in Assouad and Quentin de Gromard (2006). The implication (2)$\Rightarrow$(1) was established by Cérou and Guyader (2006). We prove the implication (1)$\Rightarrow$(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).
Similar Papers
Strong Consistency of Sparse K-means Clustering
Statistics Theory
Groups similar data points together, even when there's a lot.
KNN and K-means in Gini Prametric Spaces
Machine Learning (CS)
Makes computer sorting better with messy data.
A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
Discrete Mathematics
Helps understand complex data patterns for better predictions.