Predictive Power of Nearest Neighbors Algorithm under Random Perturbation
This work addresses robustness in nearest neighbors algorithms for machine learning practitioners, but it is incremental as it builds on existing theoretical frameworks.
The paper analyzes the effect of random perturbations on test data in the k-NN algorithm, showing that asymptotic regret remains unchanged below a critical corruption level but deteriorates polynomially above it, and finds that noise injection does not improve performance in the initial large-corruption regime.
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 \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.