Analyzing the Robustness of Nearest Neighbors to Adversarial Examples

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.

References in corpus (10)

• Explaining and Harnessing Adversarial Examples
• Intriguing properties of neural networks
• Towards Deep Learning Models Resistant to Adversarial Attacks
• Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation
• Robustness of classifiers: from adversarial to random noise
• Towards Proving the Adversarial Robustness of Deep Neural Networks
• Rates of Convergence for Nearest Neighbor Classification
• The Limitations of Deep Learning in Adversarial Settings

Cited by in corpus (31)

• Adversarially Robust Generalization Requires More Data
• Robustness May Be at Odds with Accuracy
• A Dual Approach to Scalable Verification of Deep Networks
• Adversarial examples from computational constraints
• Rademacher Complexity for Adversarially Robust Generalization
• How to Certify Machine Learning Based Safety-critical Systems? A Systematic Literature Review
• A Closer Look at Accuracy vs. Robustness
• On the Geometry of Adversarial Examples
• Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks
• Defending Against Adversarial Examples with K-Nearest Neighbor
• PAC-learning in the presence of evasion adversaries
• On the Resistance of Nearest Neighbor to Random Noisy Labels
• Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics
• Distributionally Robust Local Non-parametric Conditional Estimation
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• Input Validation for Neural Networks via Runtime Local Robustness Verification
• Automated Poisoning Attacks and Defenses in Malware Detection Systems: An Adversarial Machine Learning Approach
• A Simple Cache Model for Image Recognition
• How Wrong Am I? - Studying Adversarial Examples and their Impact on Uncertainty in Gaussian Process Machine Learning Models
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
• On Convergence of Nearest Neighbor Classifiers over Feature Transformations
• A Unified Game-Theoretic Interpretation of Adversarial Robustness
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams
• When are Non-Parametric Methods Robust?
• Sample Complexity of Adversarially Robust Linear Classification on Separated Data
• Resilience from Diversity: Population-based approach to harden models against adversarial attacks
• Predictive Power of Nearest Neighbors Algorithm under Random Perturbation
• Distributed Nearest Neighbor Classification
• Consistent Non-Parametric Methods for Maximizing Robustness
• ASK: Adversarial Soft k-Nearest Neighbor Attack and Defense
• Adversarial Examples and Metrics