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 (7)

• Explaining and Harnessing Adversarial Examples
• Towards Deep Learning Models Resistant to Adversarial Attacks
• 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

Cited by in corpus (30)

• 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
• PAC-learning in the presence of evasion adversaries
• Defending Against Adversarial Examples with K-Nearest Neighbor
• Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• Distributionally Robust Local Non-parametric Conditional Estimation
• Automated Poisoning Attacks and Defenses in Malware Detection Systems: An Adversarial Machine Learning Approach
• Input Validation for Neural Networks via Runtime Local Robustness Verification
• 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
• Resilience from Diversity: Population-based approach to harden models against adversarial attacks
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams
• Sample Complexity of Adversarially Robust Linear Classification on Separated Data
• When are Non-Parametric Methods Robust?
• Predictive Power of Nearest Neighbors Algorithm under Random Perturbation
• Distributed Nearest Neighbor Classification
• ASK: Adversarial Soft k-Nearest Neighbor Attack and Defense
• Adversarial Examples and Metrics
• Consistent Non-Parametric Methods for Maximizing Robustness