Predictive Power of Nearest Neighbors Algorithm under Random Perturbation

Yue Xing, Qifan Song, Guang Cheng
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:496-504, 2021.

Abstract

This work investigates the predictive performance of the classical k Nearest Neighbors (k-NN) algorithm when the testing data are corrupted by random perturbation. The impact of corruption level on the asymptotic regret is carefully characterized and we reveal a phase-transition phenomenon that, when the corruption level of the random perturbation ω 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. More importantly, the regret of k-NN classifier heuristically matches the rate of minimax regret for randomly perturbed testing data, thus implies the strong robustness of k-NN against random perturbation on testing data. In fact, we show that the classical k-NN can achieve no worse predictive performance, compared to the NN classifiers trained via the popular noise-injection strategy. Our numerical experiment also illustrates that combining k-NN component with modern learning algorithms will inherit the strong robustness of k-NN. 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-xing21a, title = { Predictive Power of Nearest Neighbors Algorithm under Random Perturbation }, author = {Xing, Yue and Song, Qifan and Cheng, Guang}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {496--504}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/xing21a/xing21a.pdf}, url = {https://proceedings.mlr.press/v130/xing21a.html}, abstract = { This work investigates the predictive performance of the classical $k$ Nearest Neighbors ($k$-NN) algorithm when the testing data are corrupted by random perturbation. The impact of corruption level on the asymptotic regret is carefully characterized and we reveal a phase-transition phenomenon that, when the corruption level of the random perturbation $\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. More importantly, the regret of $k$-NN classifier heuristically matches the rate of minimax regret for randomly perturbed testing data, thus implies the strong robustness of $k$-NN against random perturbation on testing data. In fact, we show that the classical $k$-NN can achieve no worse predictive performance, compared to the NN classifiers trained via the popular noise-injection strategy. Our numerical experiment also illustrates that combining $k$-NN component with modern learning algorithms will inherit the strong robustness of $k$-NN. 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. } }
Endnote
%0 Conference Paper %T Predictive Power of Nearest Neighbors Algorithm under Random Perturbation %A Yue Xing %A Qifan Song %A Guang Cheng %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-xing21a %I PMLR %P 496--504 %U https://proceedings.mlr.press/v130/xing21a.html %V 130 %X This work investigates the predictive performance of the classical $k$ Nearest Neighbors ($k$-NN) algorithm when the testing data are corrupted by random perturbation. The impact of corruption level on the asymptotic regret is carefully characterized and we reveal a phase-transition phenomenon that, when the corruption level of the random perturbation $\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. More importantly, the regret of $k$-NN classifier heuristically matches the rate of minimax regret for randomly perturbed testing data, thus implies the strong robustness of $k$-NN against random perturbation on testing data. In fact, we show that the classical $k$-NN can achieve no worse predictive performance, compared to the NN classifiers trained via the popular noise-injection strategy. Our numerical experiment also illustrates that combining $k$-NN component with modern learning algorithms will inherit the strong robustness of $k$-NN. 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.
APA
Xing, Y., Song, Q. & Cheng, G.. (2021). Predictive Power of Nearest Neighbors Algorithm under Random Perturbation . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:496-504 Available from https://proceedings.mlr.press/v130/xing21a.html.

Related Material