Robustness for Non-Parametric Classification: A Generic Attack and Defense
This work addresses adversarial robustness for non-parametric classifiers like nearest neighbors and decision trees, providing a broadly applicable baseline, though it is incremental in building on existing robustness research.
The authors tackled the problem of adversarial robustness for non-parametric classifiers by developing a generic attack and a defense method called adversarial pruning, which preprocesses datasets to improve separation and approximates an optimal robust classifier, showing competitive or better performance compared to prior work.
Adversarially robust machine learning has received much recent attention. However, prior attacks and defenses for non-parametric classifiers have been developed in an ad-hoc or classifier-specific basis. In this work, we take a holistic look at adversarial examples for non-parametric classifiers, including nearest neighbors, decision trees, and random forests. We provide a general defense method, adversarial pruning, that works by preprocessing the dataset to become well-separated. To test our defense, we provide a novel attack that applies to a wide range of non-parametric classifiers. Theoretically, we derive an optimally robust classifier, which is analogous to the Bayes Optimal. We show that adversarial pruning can be viewed as a finite sample approximation to this optimal classifier. We empirically show that our defense and attack are either better than or competitive with prior work on non-parametric classifiers. Overall, our results provide a strong and broadly-applicable baseline for future work on robust non-parametrics. Code available at https://github.com/yangarbiter/adversarial-nonparametrics/ .