Estimation by the nearest neighbor rule under arbitrary sampling

We introduce a new estimation problem in which the samples can be chosen arbitrarily. We show that for every sequence of samples the asymptotic time-average of nearest neighbor risks equals twice the time-average of the conditional Bayes risks of the sequence. Rates of convergence for nearest neighbor estimation are established in terms of metric covering numbers of the underlying space. In particular, for compact subsets of R^r the convergence rate of the time-averaged risk is O(1/n²r/)