An adaptive multiclass nearest neighbor classifier^*

¹ National Research University Higher School of Economics, 20 Myasnitskaya ulitsa, 101000 Moscow, RF.
² Institute for Information Transmission Problems RAS, Bolshoy Karetny per. 19, 127051 Moscow, RF.
³ Weierstrass Institute and Humboldt University, Mohrenstr. 39, 10117 Berlin, Germany.

^** Corresponding author: npuchkin@hse.ru

Received: 23 December 2018
Accepted: 24 October 2019

Abstract

We consider a problem of multiclass classification, where the training sample S_n={(X_i,Y_i)}ⁿ_i=1 is generated from the model ℙ(Y = m|X = x) = η_m(x), 1 ≤ m ≤ M, and η₁(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 η₁(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 n₁, …, n_K, compute corresponding n_k-nearest-neighbor estimates for each m and each n_k 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.