# Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 20 May 2021.

## Builds on (most cited first, 7 of 7)

- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Transfer Learning for Nonparametric Classification: Minimax Rate and Adaptive Classifier](https://mlsanity.com/paper/1906.02903/) (2019)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [An adaptive nearest neighbor rule for classification](https://mlsanity.com/paper/1905.12717/) (2019)
- [Distributed Generalized Cross-Validation for Divide-and-Conquer Kernel Ridge Regression and its Asymptotic Optimality](https://mlsanity.com/paper/1612.05907/) (2016)
- [Rates of Convergence for Large-scale Nearest Neighbor Classification](https://mlsanity.com/paper/1909.01464/) (2019)

## Abstract (arXiv)

When data is of an extraordinarily large size or physically stored in different locations, the distributed nearest neighbor (NN) classifier is an attractive tool for classification. We propose a novel distributed adaptive NN classifier for which the number of nearest neighbors is a tuning parameter stochastically chosen by a data-driven criterion. An early stopping rule is proposed when searching for the optimal tuning parameter, which not only speeds up the computation but also improves the finite sample performance of the proposed Algorithm. Convergence rate of excess risk of the distributed adaptive NN classifier is investigated under various sub-sample size compositions. In particular, we show that when the sub-sample sizes are sufficiently large, the proposed classifier achieves the nearly optimal convergence rate. Effectiveness of the proposed approach is demonstrated through simulation studies as well as an empirical application to a real-world dataset.