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

Lu Wang, Xuanqing Liu, Jinfeng Yi, Zhi-Hua Zhou, Cho-Jui HsieharXiv 2019 · OpenReview

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.

Introduction

Adversarial robustness—the study of how small, imperceptible changes to input data can fool a model—has been dominated by research into deep neural networks (DNNs). However, Nearest Neighbor (NN) classifiers remain a staple of machine learning due to their simplicity and theoretical properties. Unlike DNNs, which are continuous functions, NN classifiers are discrete "step functions." This makes them "gradient-blind"; standard backpropagation-based attacks cannot be used to find their weaknesses. Previous attempts to evaluate NN robustness relied on "substitute models" or simple heuristics, which are often suboptimal and lack theoretical guarantees. This work addresses this gap by providing a method to precisely calculate the smallest possible perturbation required to change an NN classifier's prediction.

Methodology

The core contribution is an efficient algorithm to find the minimum adversarial perturbation for 1-NN classifiers by framing it as a series of convex quadratic programming (QP) problems.

Quadratic Programming Formulation

The problem of finding the closest point with a different label is decomposed into subproblems, each representing the distance from a test point to a specific "Voronoi cell" belonging to a different class. For a 1-NN model, the decision boundaries are formed by the intersections of bisection hyperplanes between data points.

Geometric intuition of finding the minimum perturbation for 1-NN and K-NN classifiers. (a) Distance to a single hyperplane. (b) Distance to an intersection of hyperplanes. (c) Voronoi cells and K-NN boundaries.

The Primal-Dual Perspective

By utilizing duality, the framework provides both attacks and verification:

  • Primal Solution: Solving the QP directly yields the exact adversarial attack, serving as an upper bound on the minimum perturbation.
  • Dual Solution: Solving the dual version provides a mathematical lower bound. If the dual solution indicates a distance of at least $r$, the model is guaranteed to be stable within that radius.

Computational Efficiency

To handle large datasets, the authors introduced sorting to find small upper bounds quickly and screening rules to skip irrelevant neighbors. A specialized Greedy Coordinate Ascent solver was also developed, exploiting problem sparsity to outperform general-purpose solvers by over 60x. For $K$-NN models where $K > 1$, the framework provides tight upper and lower bounds, as exact computation becomes combinatorially difficult.

Experimental Evaluation

The approach was evaluated on MNIST, Fashion-MNIST, and Binary-MNIST datasets.

Key Results

  • Exactness: For 1-NN, the algorithm identifies the true minimum perturbation. Previous heuristic attacks were found to be significantly suboptimal (e.g., finding a perturbation of 1.85 when the true minimum was 1.49).
  • Speed: Screening rules allowed the algorithm to solve only ~2.5 subproblems on average out of 54,000 candidates on MNIST.
  • Verification: The dual-based verifier provided lower bounds very close to the actual minimum perturbation, enabling practical safety audits.
  • K-NN Scaling: As $K$ increases, model robustness generally improves. The proposed "QP-greedy" attack consistently outperformed existing heuristics.

Discussion and Insights

A significant finding is that while finding minimum perturbations for ReLU networks is NP-hard, it is solvable in polynomial time for 1-NN. Furthermore, on datasets like MNIST, a basic 1-NN model can achieve better verifiable robust error than a Convolutional Neural Network (CNN). While the CNN has higher overall accuracy, it is more susceptible to tiny perturbations compared to the geometrically defined boundaries of the 1-NN.

Conclusion

This work provides the first exact algorithm for 1-NN robustness and tight bounds for $K$-NN. While 1-NN performs well on simpler datasets, scaling to complex data like ImageNet remains a challenge due to the lower "clean" accuracy of NN models compared to DNNs. Future research may explore "Deep Nearest Neighbors" to combine DNN representation power with the verifiable properties of NN classifiers.

Summary updated

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.
BibTeX
@misc{wang2019evaluating,
  author = {Lu Wang and Xuanqing Liu and Jinfeng Yi and Zhi-Hua Zhou and Cho-Jui Hsieh},
  title = {{Evaluating the Robustness of Nearest Neighbor Classifiers: A Primal-Dual Perspective}},
  year = {2019},
  eprint = {1906.03972},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.03972},
}

Loading related content...

Figure