mlsanityData to 14 Oct 2026

Analyzing the Robustness of Nearest Neighbors to Adversarial Examples

arXiv 1706.03922 ↗First posted 13 Jun 2017stat.ML cs.CR cs.LGcited by 36

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 14; 2022: 10; 2023: 2; 2024: 6; 2025: 4.

36 papers.

Sort:

By area:

  1. 2024RigorLLM: Resilient Guardrails for Large Language Models against Undesired Contentcited by 68
  2. 2021How to Certify Machine Learning Based Safety-critical Systems? A Systematic Literature Reviewcited by 39
  3. 2022Probabilistically Robust Learning: Balancing Average- and Worst-case Performancecited by 37
  4. 2021Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learningcited by 29
  5. 2022From Noisy Prediction to True Label: Noisy Prediction Calibration via Generative Modelcited by 22
  6. 2022Verification-Aided Deep Ensemble Selectioncited by 18
  7. 2021A Unified Game-Theoretic Interpretation of Adversarial Robustnesscited by 17
  8. 2021Connecting Interpretability and Robustness in Decision Trees through Separationcited by 16
  9. 2022GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networkscited by 14
  10. 2021Robust Optimal Classification Trees Against Adversarial Examplescited by 11
  11. 2021Understanding Generalization in Adversarial Training via the Bias-Variance Decompositioncited by 10
  12. 2023It Is All About Data: A Survey on the Effects of Data on Adversarial Robustnesscited by 9
24 more
  1. 2021Consistent Non-Parametric Methods for Maximizing Robustnesscited by 7
  2. 2022Robust Empirical Risk Minimization with Tolerancecited by 6
  3. 2024Adversarial Feature Alignment: Balancing Robustness and Accuracy in Deep Learning via Adversarial Trainingcited by 5
  4. 2021ASK: Adversarial Soft k-Nearest Neighbor Attack and Defensecited by 4
  5. 2025CEHR-XGPT: A Scalable Multi-Task Foundation Model for Electronic Health Recordscited by 4
  6. 2024Buster: Implanting Semantic Backdoor into Text Encoder to Mitigate NSFW Content Generationcited by 3
  7. 2025Pre-training CLIP against Data Poisoning with Optimal Transport-based Matching and Alignmentcited by 3
  8. 2021Attack Transferability Characterization for Adversarially Robust Multi-label Classificationcited by 2
  9. 2022Adversarial Attack and Defense for Non-Parametric Two-Sample Testscited by 2
  10. 2022Provably Adversarially Robust Nearest Prototype Classifierscited by 2
  11. 2024Minimax rates of convergence for nonparametric regression under adversarial attackscited by 2
  12. 2025Explaining the Success of Nearest Neighbor Methods in Predictioncited by 2
  13. 2021Robust Certification for Laplace Learning on Geometric Graphscited by 1
  14. 2021Resilience from Diversity: Population-based approach to harden models against adversarial attackscited by 1
  15. 2022Benefit of Interpolation in Nearest Neighbor Algorithmscited by 1
  16. 2022Chaos Theory and Adversarial Robustnesscited by 1
  17. 2023Systematic Testing of the Data-Poisoning Robustness of KNNcited by 1
  18. 2025Adversarial Robustness of Nonparametric Regressioncited by 1
  19. 2021A Unified Game-Theoretic Interpretation of Adversarial Robustnesscited by 0
  20. 2021On the (Un-)Avoidability of Adversarial Examplescited by 0
  21. 2021kNet: A Deep kNN Network To Handle Label Noisecited by 0
  22. 2022Training-Time Attacks against k-Nearest Neighborscited by 0
  23. 2024Robustness bounds on the successful adversarial examples in probabilistic models: Implications from Gaussian processescited by 0
  24. 2024On adversarial training and the 1 Nearest Neighbor classifiercited by 0