# Predictive Power of Nearest Neighbors Algorithm under Random Perturbation

arXiv: https://arxiv.org/abs/2002.05304 · HTML: https://mlsanity.com/paper/2002.05304/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2020.

## Built on by (most cited first, 2 of 2)

- [Minimax rates of convergence for nonparametric regression under adversarial attacks](https://mlsanity.com/paper/2410.09402/) (2024)
- [Benefit of Interpolation in Nearest Neighbor Algorithms](https://mlsanity.com/paper/2202.11817/) (2022)

## Abstract (arXiv)

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 ω is below a critical order (i.e., small-ω regime), the asymptotic regret remains the same; when it is beyond that order (i.e., large-ω 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-ω 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 citexue2017achieving 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.