Universal consistency of the k-NN rule in metric spaces and Nagata dimension^*,**

¹ Department of Mathematics, Kyoto University, Kitashirakawa Oiwake-cho, Sakyo-ku 606-8502, Japan.
² Department of Mathematical Engineering, Musashino University, 1 Chome-1-20 Shinmachi, Nishitokyo, Tokyo 202-8585, Japan.
³ Instituto de Matemática e Estatística, Universidade Federal da Bahia, Ondina, Salvador–BA, 40.170-115, Brazil.
⁴ Department of Mathematics and Statistics, University of Ottawa, Ottawa, ON K1N 6N5, Canada.

^*** Corresponding author: vpest283@uottawa.ca

Received: 28 February 2020
Accepted: 22 June 2020

Abstract

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érou 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.