Measuring Adversarial Robustness using a Voronoi-Epsilon Adversary
This work addresses a foundational issue in adversarial machine learning by refining robustness metrics, though it is incremental as it modifies existing adversary definitions rather than introducing a new paradigm.
The paper tackles the problem of the inherent tradeoff between accuracy and adversarial accuracy in adversarial robustness evaluations by proposing a Voronoi-epsilon adversary that constrains adversarial examples using both Voronoi cells and ε-balls, avoiding this tradeoff on training data even with large ε, and demonstrates that a nearest neighbor classifier is maximally robust against this adversary.
Previous studies on robustness have argued that there is a tradeoff between accuracy and adversarial accuracy. The tradeoff can be inevitable even when we neglect generalization. We argue that the tradeoff is inherent to the commonly used definition of adversarial accuracy, which uses an adversary that can construct adversarial points constrained by $ε$-balls around data points. As $ε$ gets large, the adversary may use real data points from other classes as adversarial examples. We propose a Voronoi-epsilon adversary which is constrained both by Voronoi cells and by $ε$-balls. This adversary balances between two notions of perturbation. As a result, adversarial accuracy based on this adversary avoids a tradeoff between accuracy and adversarial accuracy on training data even when $ε$ is large. Finally, we show that a nearest neighbor classifier is the maximally robust classifier against the proposed adversary on the training data.