Mixed Nash Equilibria in the Adversarial Examples Game
arXiv:2102.06905
Abstract
This paper tackles the problem of adversarial examples from a game theoretic point of view. We study the open question of the existence of mixed Nash equilibria in the zero-sum game formed by the attacker and the classifier. While previous works usually allow only one player to use randomized strategies, we show the necessity of considering randomization for both the classifier and the attacker. We demonstrate that this game has no duality gap, meaning that it always admits approximate Nash equilibria. We also provide the first optimization algorithms to learn a mixture of classifiers that approximately realizes the value of this game, \emph{i.e.} procedures to build an optimally robust randomized classifier.
References in corpus (9)
- Certified Adversarial Robustness via Randomized Smoothing
- The Space of Transferable Adversarial Examples
- Certifying Some Distributional Robustness with Principled Adversarial Training
- Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examples
- Minimax Statistical Learning with Wasserstein Distances
- Randomized Prediction Games for Adversarial Machine Learning
- Lower Bounds on Adversarial Robustness from Optimal Transport
- Robust Attacks against Multiple Classifiers
- On Linear Optimization over Wasserstein Balls