Randomization matters. How to defend against strong adversarial attacks
This addresses the challenge of defending against strong adversarial attacks in machine learning, offering a novel theoretical and practical approach with broad implications for security-critical applications.
The paper tackles the problem of ensuring optimal robustness against all adversarial attacks by showing that deterministic classifiers cannot achieve a Nash equilibrium, but randomized classifiers can outperform them under mild conditions, leading to a new algorithm that empirically outperforms Adversarial Training against state-of-the-art attacks with considerable gains.
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.