# When are Non-Parametric Methods Robust?

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2020.

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

- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [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)
- [Consistent Non-Parametric Methods for Maximizing Robustness](https://mlsanity.com/paper/2102.09086/) (2021)
- [Analyzing Explainer Robustness via Probabilistic Lipschitzness of Prediction Functions](https://mlsanity.com/paper/2206.12481/) (2022)
- [Robust Empirical Risk Minimization with Tolerance](https://mlsanity.com/paper/2210.00635/) (2022)
- [The Adversarial Consistency of Surrogate Risks for Binary Classification](https://mlsanity.com/paper/2305.09956/) (2023)
- [The Consistency of Adversarial Training for Binary Classification](https://mlsanity.com/paper/2206.09099/) (2022)
- [Adversarial Attack and Defense for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2202.03077/) (2022)
- [Faithfulness and the Notion of Adversarial Sensitivity in NLP Explanations](https://mlsanity.com/paper/2409.17774/) (2024)
- [Minimax rates of convergence for nonparametric regression under adversarial attacks](https://mlsanity.com/paper/2410.09402/) (2024)
- [Analysis of Robustness of a Large Game Corpus](https://mlsanity.com/paper/2504.03940/) (2025)
- [On the (Un-)Avoidability of Adversarial Examples](https://mlsanity.com/paper/2106.13326/) (2021)
- [Training-Time Attacks against k-Nearest Neighbors](https://mlsanity.com/paper/2208.07272/) (2022)

## Abstract (arXiv)

A growing body of research has shown that many classifiers are susceptible to emadversarial 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.