When are Non-Parametric Methods Robust?
arXiv:2003.06121
Abstract
A growing body of research has shown that many classifiers are susceptible to {\em{adversarial examples}} -- small strategic modifications to test inputs that lead to misclassification. In this work, we study general non-parametric methods, with a view towards understanding when they are robust to these modifications. We establish general conditions under which non-parametric methods are r-consistent -- in the sense that they converge to optimally robust and accurate classifiers in the large sample limit. Concretely, our results show that when data is well-separated, nearest neighbors and kernel classifiers are r-consistent, while histograms are not. For general data distributions, we prove that preprocessing by Adversarial Pruning (Yang et. al., 2019) -- that makes data well-separated -- followed by nearest neighbors or kernel classifiers also leads to r-consistency.
arXiv commentaccepted to ICML 2020
References in corpus (10)
- Delving into Transferable Adversarial Examples and Black-box Attacks
- Certified Defenses against Adversarial Examples
- Adversarially Robust Generalization Requires More Data
- Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
- Towards Proving the Adversarial Robustness of Deep Neural Networks
- Evasion and Hardening of Tree Ensemble Classifiers
- Analyzing the Robustness of Nearest Neighbors to Adversarial Examples
- VC Classes are Adversarially Robustly Learnable, but Only Improperly
- Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks
- Universal Bayes consistency in metric spaces