  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.
