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.

本篇论文的研究内容为：计算最小对抗性扰动的问题。研究者们提出了第一个能够计算最小对抗性扰动的算法，将问题用凸二次规划问题的列表进行了表示，用于 1-NN 模型的算法能够有效地解决这个问题。对于更大的 $K$-NN 模型，我们表明同样的表示形式可以帮助我们有效地计算最小对抗性扰动的上限和下限，这可用于攻击和验证。