Analyzing the Robustness of Nearest Neighbors to Adversarial Examples

Yizhen Wang, Somesh Jha, Kamalika Chaudhuri
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:5133-5142, 2018.

Abstract

Motivated by safety-critical applications, test-time attacks on classifiers via adversarial examples has recently received a great deal of attention. However, there is a general lack of understanding on why adversarial examples arise; whether they originate due to inherent properties of data or due to lack of training samples remains ill-understood. In this work, we introduce a theoretical framework analogous to bias-variance theory for understanding these effects. We use our framework to analyze the robustness of a canonical non-parametric classifier {–} the k-nearest neighbors. Our analysis shows that its robustness properties depend critically on the value of k {–} the classifier may be inherently non-robust for small k, but its robustness approaches that of the Bayes Optimal classifier for fast-growing k. We propose a novel modified 1-nearest neighbor classifier, and guarantee its robustness in the large sample limit. Our experiments suggest that this classifier may have good robustness properties even for reasonable data set sizes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-wang18c, title = {Analyzing the Robustness of Nearest Neighbors to Adversarial Examples}, author = {Wang, Yizhen and Jha, Somesh and Chaudhuri, Kamalika}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {5133--5142}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/wang18c/wang18c.pdf}, url = {https://proceedings.mlr.press/v80/wang18c.html}, abstract = {Motivated by safety-critical applications, test-time attacks on classifiers via adversarial examples has recently received a great deal of attention. However, there is a general lack of understanding on why adversarial examples arise; whether they originate due to inherent properties of data or due to lack of training samples remains ill-understood. In this work, we introduce a theoretical framework analogous to bias-variance theory for understanding these effects. We use our framework to analyze the robustness of a canonical non-parametric classifier {–} the k-nearest neighbors. Our analysis shows that its robustness properties depend critically on the value of k {–} the classifier may be inherently non-robust for small k, but its robustness approaches that of the Bayes Optimal classifier for fast-growing k. We propose a novel modified 1-nearest neighbor classifier, and guarantee its robustness in the large sample limit. Our experiments suggest that this classifier may have good robustness properties even for reasonable data set sizes.} }
Endnote
%0 Conference Paper %T Analyzing the Robustness of Nearest Neighbors to Adversarial Examples %A Yizhen Wang %A Somesh Jha %A Kamalika Chaudhuri %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-wang18c %I PMLR %P 5133--5142 %U https://proceedings.mlr.press/v80/wang18c.html %V 80 %X Motivated by safety-critical applications, test-time attacks on classifiers via adversarial examples has recently received a great deal of attention. However, there is a general lack of understanding on why adversarial examples arise; whether they originate due to inherent properties of data or due to lack of training samples remains ill-understood. In this work, we introduce a theoretical framework analogous to bias-variance theory for understanding these effects. We use our framework to analyze the robustness of a canonical non-parametric classifier {–} the k-nearest neighbors. Our analysis shows that its robustness properties depend critically on the value of k {–} the classifier may be inherently non-robust for small k, but its robustness approaches that of the Bayes Optimal classifier for fast-growing k. We propose a novel modified 1-nearest neighbor classifier, and guarantee its robustness in the large sample limit. Our experiments suggest that this classifier may have good robustness properties even for reasonable data set sizes.
APA
Wang, Y., Jha, S. & Chaudhuri, K.. (2018). Analyzing the Robustness of Nearest Neighbors to Adversarial Examples. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:5133-5142 Available from https://proceedings.mlr.press/v80/wang18c.html.

Related Material