SupplementaryMaterial: ExtrapolationTowardsImaginary0-NearestNeighbour andItsImprovedConvergenceRate ARelatedworks

In this section, we describe Nadaraya-Watson (NW) classifier, Local Polynomial (LP) classifier and their convergence rates (Audibert & Tsybakov, 2007). In what follows,K: X R represents a kernel function, e.g., Gaussian kernel K(X):=exp( kXk22),andh>0representsabandwidth. LP classifier is thus proved to be an optimal classifier in this sense. The two error terms are in fact combined asδβ,r(X) = O(rβ), because 2bβ/2c+2 β. In step (i), queries are first classified into two different cases, i.e., (X) io and (X) > io.