Evaluating the Robustness of Nearest Neighbor Classifiers: A Primal-Dual Perspective

2019/06/10 by Lu Wang, Wang, Lu, Xuanqing Liu +7 · 1 citation
Computer Science · #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.1906.03972

openalex publication_date 2019/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of computing the minimum adversarial perturbation of the Nearest Neighbor (NN) classifiers. Previous attempts either conduct attacks on continuous approximations of NN models or search for the perturbation by some heuristic methods. In this paper, we propose the first algorithm that is able to compute the minimum adversarial perturbation. The main idea is to formulate the problem as a list of convex quadratic programming (QP) problems that can be efficiently solved by the proposed algorithms for 1-NN models. Furthermore, we show that dual solutions for these QP problems could give us a valid lower bound of the adversarial perturbation that can be used for formal robustness verification, giving us a nice view of attack/verification for NN models. For K-NN models with larger K, we show that the same formulation can help us efficiently compute the upper and lower bounds of the minimum adversarial perturbation, which can be used for attack and verification.

Citations

• Gradient-based learning applied to document recognition
• Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning
• Efficient Formal Safety Analysis of Neural Networks
• A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks
• Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach
• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach

Cited by

• Distributionally Robust Local Non-parametric Conditional Estimation

Related

• Defending Against Adversarial Examples with K-Nearest Neighbor
• Adversarial Examples for k-Nearest Neighbor Classifiers Based on\n Higher-Order Voronoi Diagrams
• AdvKnn: Adversarial Attacks On K-Nearest Neighbor Classifiers With Approximate Gradients
• On the Robustness of Deep K-Nearest Neighbors
• Minimum-Norm Adversarial Examples on KNN and KNN-Based Models