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

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2020.

## Built on by (most cited first, 4 of 4)

- [Universal consistency of the k-NN rule in metric spaces and Nagata dimension. II](https://mlsanity.com/paper/2305.17282/) (2023)
- [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)
- [k-Nearest Neighbors in Gromov--Wasserstein Space](https://mlsanity.com/paper/2606.10295/) (2026)

## Abstract (arXiv)

The k nearest neighbour learning rule (under the uniform distance tie breaking) is universally consistent in every metric space X that is sigma-finite dimensional in the sense of Nagata. This was pointed out by C'erou and Guyader (2006) as a consequence of the main result by those authors, combined with a theorem in real analysis sketched by D. Preiss (1971) (and elaborated in detail by Assouad and Quentin de Gromard (2006)). We show that it is possible to give a direct proof along the same lines as the original theorem of Charles J. Stone (1977) about the universal consistency of the k-NN classifier in the finite dimensional Euclidean space. The generalization is non-trivial because of the distance ties being more prevalent in the non-euclidean setting, and on the way we investigate the relevant geometric properties of the metrics and the limitations of the Stone argument, by constructing various examples.