# An adaptive multiclass nearest neighbor classifier

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2018.

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

- [On Error and Compression Rates for Prototype Rules](https://mlsanity.com/paper/2206.08014/) (2022)
- [On Rate-Optimal Partitioning Classification from Observable and from Privatised Data](https://mlsanity.com/paper/2312.14889/) (2023)
- [On public and private binary classification with metric space valued predictors](https://mlsanity.com/paper/2605.31184/) (2026)

## Abstract (arXiv)

We consider a problem of multiclass classification, where the training sample Sn = (Xi, Yi)i=1n is generated from the model mathbb P(Y = m | X = x) = ηm(x), 1 ≤ m ≤ M, and η1(x), dots, ηM(x) are unknown α-Holder continuous functions.Given a test point X, our goal is to predict its label. A widely used mathsf k-nearest-neighbors classifier constructs estimates of η1(X), dots, ηM(X) and uses a plug-in rule for the prediction. However, it requires a proper choice of the smoothing parameter mathsf k, which may become tricky in some situations. In our solution, we fix several integers n1, dots, nK, compute corresponding nk-nearest-neighbor estimates for each m and each nk and apply an aggregation procedure. We study an algorithm, which constructs a convex combination of these estimates such that the aggregated estimate behaves approximately as well as an oracle choice. We also provide a non-asymptotic analysis of the procedure, prove its adaptation to the unknown smoothness parameter α and to the margin and establish rates of convergence under mild assumptions.