# Robustness for Non-Parametric Classification: A Generic Attack and Defense

arXiv: https://arxiv.org/abs/1906.03310 · HTML: https://mlsanity.com/paper/1906.03310/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2019.

## Built on by (most cited first, 12 of 12)

- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classification](https://mlsanity.com/paper/2206.09098/) (2022)
- [Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition](https://mlsanity.com/paper/2103.09947/) (2021)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Data Quality Matters For Adversarial Training: An Empirical Study](https://mlsanity.com/paper/2102.07437/) (2021)
- [Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker](https://mlsanity.com/paper/2302.10722/) (2023)
- [Adversarial Attack and Defense for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2202.03077/) (2022)
- [Minimax rates of convergence for nonparametric regression under adversarial attacks](https://mlsanity.com/paper/2410.09402/) (2024)
- [Exploring Adversarial Examples for Efficient Active Learning in Machine Learning Classifiers](https://mlsanity.com/paper/2109.10770/) (2021)
- [Adversarial Robustness of Nonparametric Regression](https://mlsanity.com/paper/2505.17356/) (2025)
- [On the (Un-)Avoidability of Adversarial Examples](https://mlsanity.com/paper/2106.13326/) (2021)

## Abstract (arXiv)

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/ .