When are Non-Parametric Methods Robust?
This work addresses the robustness of non-parametric methods to adversarial attacks for machine learning practitioners, providing theoretical guarantees but is incremental as it builds on existing concepts like r-consistency and Adversarial Pruning.
The paper tackles the problem of adversarial examples in non-parametric classifiers by establishing conditions under which methods like nearest neighbors and kernel classifiers converge to optimally robust and accurate classifiers in the large sample limit, showing they are r-consistent when data is well-separated or after preprocessing with Adversarial Pruning.
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.