Pointwise adaptation via stagewise aggregation of local estimates for multiclass classification

We consider a problem of multiclass classification, where the training sample Sn = {(Xi, Yi)}n i=1 is generated from the model P(Y = m|X = x) = m(x), 1 6 m 6 M, and 1(x), . . . , M(x) are unknown Lip- schitz functions. Given a test point X, our goal is to estimate 1(X), . . . , M(X). An approach based on nonparametric smoothing uses a localization technique, i.e. the weight of observation (Xi, Yi) depends on the distance between Xi and X. However, local estimates strongly depend on localiz- ing scheme. In our solution we fix several schemes W1, . . . ,WK, compute corresponding local estimates e(1), . . . , e(K) for each of them and apply an aggregation procedure. We propose an algorithm, which constructs a con- vex combination of the estimates e(1), . . . , e(K) such that the aggregated estimate behaves approximately as well as the best one from the collection e(1), . . . , e(K). We also study theoretical properties of the procedure, prove oracle results and establish rates of convergence under mild assumptions.