?
An adaptive multiclass nearest neighbor classifier
We consider a problem of multiclass classification, where the training sample Sn={(Xi,Yi)}ni=1 is generated from the model ℙ(Y=m|X=x)=ηm(x), 1≤m≤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 𝗄-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 𝗄, which may become tricky in some situations. In our solution, we fix several integers n1,…,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.