An adaptive multiclass nearest neighbor classifier

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.