Fast and Multiphase Rates for Nearest Neighbor Classifiers

Pengkun Yang, Jingzhao Zhang

We study the scaling of classification error rates with respect to the size of the training dataset. In contrast to classical results where rates are minimax optimal for a problem…