Predictive Power of Nearest Neighbors Algorithm under Random
  Perturbation
  We consider a data corruption scenario in the classical $k$ Nearest Neighbors
($k$-NN) algorithm, that is, the testing data are randomly perturbed. Under
such a scenario, the impact of corruption level on the asymptotic regret is
carefully characterized. In particular, our theoretical analysis reveals a
phase transition phenomenon that, when the corruption level $\omega$ is below a
critical order (i.e., small-$\omega$ regime), the asymptotic regret remains the
same; when it is beyond that order (i.e., large-$\omega$ regime), the
asymptotic regret deteriorates polynomially. Surprisingly, we obtain a negative
result that the classical noise-injection approach will not help improve the
testing performance in the beginning stage of the large-$\omega$ regime, even
in the level of the multiplicative constant of asymptotic regret. As a
technical by-product, we prove that under different model assumptions, the
pre-processed 1-NN proposed in \cite{xue2017achieving} will at most achieve a
sub-optimal rate when the data dimension $d>4$ even if $k$ is chosen optimally
in the pre-processing step.
