Randomization matters. How to defend against strong adversarial attacks
arXiv:2002.11565
Abstract
Is there a classifier that ensures optimal robustness against all adversarial attacks? This paper answers this question by adopting a game-theoretic point of view. We show that adversarial attacks and defenses form an infinite zero-sum game where classical results (e.g. Sion theorem) do not apply. We demonstrate the non-existence of a Nash equilibrium in our game when the classifier and the Adversary are both deterministic, hence giving a negative answer to the above question in the deterministic regime. Nonetheless, the question remains open in the randomized regime. We tackle this problem by showing that, undermild conditions on the dataset distribution, any deterministic classifier can be outperformed by a randomized one. This gives arguments for using randomization, and leads us to a new algorithm for building randomized classifiers that are robust to strong adversarial attacks. Empirical results validate our theoretical analysis, and show that our defense method considerably outperforms Adversarial Training against state-of-the-art attacks.
References in corpus (15)
- Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
- On Evaluating Adversarial Robustness
- Improving Adversarial Robustness via Promoting Ensemble Diversity
- Certified Adversarial Robustness with Additive Noise
- Adversarial vulnerability for any classifier
- On Adaptive Attacks to Adversarial Example Defenses
- Adversarial examples from computational constraints
- Robustness of classifiers: from adversarial to random noise
- Minimax Statistical Learning with Wasserstein Distances
- Randomized Prediction Games for Adversarial Machine Learning
- Feature Squeezing Mitigates and Detects Carlini/Wagner Adversarial Examples
- Theoretical evidence for adversarial robustness through randomization
- Lower Bounds on Adversarial Robustness from Optimal Transport
- On the Hardness of Robust Classification
- Robust Attacks against Multiple Classifiers