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

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.

References in corpus (8)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning
• Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning
• Efficient Formal Safety Analysis of Neural Networks
• Evasion and Hardening of Tree Ensemble Classifiers

Cited by in corpus (5)

• Distributionally Robust Local Non-parametric Conditional Estimation
• Spanning Attack: Reinforce Black-box Attacks with Unlabeled Data
• KNN-enhanced Deep Learning Against Noisy Labels
• Provably Robust Metric Learning
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams