Minimax Rate Optimal Adaptive Nearest Neighbor Classification and
  Regression
  k Nearest Neighbor (kNN) method is a simple and popular statistical method
for classification and regression. For both classification and regression
problems, existing works have shown that, if the distribution of the feature
vector has bounded support and the probability density function is bounded away
from zero in its support, the convergence rate of the standard kNN method, in
which k is the same for all test samples, is minimax optimal. On the contrary,
if the distribution has unbounded support, we show that there is a gap between
the convergence rate achieved by the standard kNN method and the minimax bound.
To close this gap, we propose an adaptive kNN method, in which different k is
selected for different samples. Our selection rule does not require precise
knowledge of the underlying distribution of features. The new proposed method
significantly outperforms the standard one. We characterize the convergence
rate of the proposed adaptive method, and show that it matches the minimax
lower bound.
