# Analyzing the Robustness of Nearest Neighbors to Adversarial Examples

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2017.

## Built on by (most cited first, 30 of 36)

- [RigorLLM: Resilient Guardrails for Large Language Models against Undesired Content](https://mlsanity.com/paper/2403.13031/) (2024)
- [How to Certify Machine Learning Based Safety-critical Systems? A Systematic Literature Review](https://mlsanity.com/paper/2107.12045/) (2021)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2110.04471/) (2021)
- [From Noisy Prediction to True Label: Noisy Prediction Calibration via Generative Model](https://mlsanity.com/paper/2205.00690/) (2022)
- [Verification-Aided Deep Ensemble Selection](https://mlsanity.com/paper/2202.03898/) (2022)
- [A Unified Game-Theoretic Interpretation of Adversarial Robustness](https://mlsanity.com/paper/2111.03536/) (2021)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks](https://mlsanity.com/paper/2201.12741/) (2022)
- [Robust Optimal Classification Trees Against Adversarial Examples](https://mlsanity.com/paper/2109.03857/) (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)
- [Robust Empirical Risk Minimization with Tolerance](https://mlsanity.com/paper/2210.00635/) (2022)
- [Adversarial Feature Alignment: Balancing Robustness and Accuracy in Deep Learning via Adversarial Training](https://mlsanity.com/paper/2402.12187/) (2024)
- [ASK: Adversarial Soft k-Nearest Neighbor Attack and Defense](https://mlsanity.com/paper/2106.14300/) (2021)
- [CEHR-XGPT: A Scalable Multi-Task Foundation Model for Electronic Health Records](https://mlsanity.com/paper/2509.03643/) (2025)
- [Buster: Implanting Semantic Backdoor into Text Encoder to Mitigate NSFW Content Generation](https://mlsanity.com/paper/2412.07249/) (2024)
- [Pre-training CLIP against Data Poisoning with Optimal Transport-based Matching and Alignment](https://mlsanity.com/paper/2509.18717/) (2025)
- [Attack Transferability Characterization for Adversarially Robust Multi-label Classification](https://mlsanity.com/paper/2106.15360/) (2021)
- [Adversarial Attack and Defense for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2202.03077/) (2022)
- [Provably Adversarially Robust Nearest Prototype Classifiers](https://mlsanity.com/paper/2207.07208/) (2022)
- [Minimax rates of convergence for nonparametric regression under adversarial attacks](https://mlsanity.com/paper/2410.09402/) (2024)
- [Explaining the Success of Nearest Neighbor Methods in Prediction](https://mlsanity.com/paper/2502.15900/) (2025)
- [Robust Certification for Laplace Learning on Geometric Graphs](https://mlsanity.com/paper/2104.10837/) (2021)
- [Resilience from Diversity: Population-based approach to harden models against adversarial attacks](https://mlsanity.com/paper/2111.10272/) (2021)
- [Benefit of Interpolation in Nearest Neighbor Algorithms](https://mlsanity.com/paper/2202.11817/) (2022)
- [Chaos Theory and Adversarial Robustness](https://mlsanity.com/paper/2210.13235/) (2022)
- [Systematic Testing of the Data-Poisoning Robustness of KNN](https://mlsanity.com/paper/2307.08288/) (2023)
- [Adversarial Robustness of Nonparametric Regression](https://mlsanity.com/paper/2505.17356/) (2025)

## Abstract (arXiv)

Motivated by safety-critical applications, test-time attacks on classifiers via adversarial examples has recently received a great deal of attention. However, there is a general lack of understanding on why adversarial examples arise; whether they originate due to inherent properties of data or due to lack of training samples remains ill-understood. In this work, we introduce a theoretical framework analogous to bias-variance theory for understanding these effects. We use our framework to analyze the robustness of a canonical non-parametric classifier - the k-nearest neighbors. Our analysis shows that its robustness properties depend critically on the value of k - the classifier may be inherently non-robust for small k, but its robustness approaches that of the Bayes Optimal classifier for fast-growing k. We propose a novel modified 1-nearest neighbor classifier, and guarantee its robustness in the large sample limit. Our experiments suggest that this classifier may have good robustness properties even for reasonable data set sizes.