An adaptive multiclass nearest neighbor classifier

Nikita Puchkin, Vladimir Spokoiny

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


We consider a problem of multiclass classification, where the training sample Sn = f(Xi; Yi)gn i=1 is generated from the model P(Y = mjX = x) = ηm(x), 1 6 m 6 M, and η1(x); : : : ; ηM(x) are unknown α-Holder continuous functions. Given a test point X, our goal is to predict its label. A widely used k-nearest-neighbors classifier constructs estimates of η1(X); : : : ; ηM(X) and uses a plug-in rule for the prediction. However, it requires a proper choice of the smoothing parameter k, which may become tricky in some situations. We fix several integers n1; : : : ; nK, com- pute 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.

Original languageEnglish
Pages (from-to)69-99
Number of pages31
JournalESAIM - Probability and Statistics
Publication statusPublished - 2020
Externally publishedYes


  • Adaptive procedures
  • K nearest neighbors
  • Multiclass classification


Dive into the research topics of 'An adaptive multiclass nearest neighbor classifier'. Together they form a unique fingerprint.

Cite this