# Randomization matters. How to defend against strong adversarial attacks

arXiv: https://arxiv.org/abs/2002.11565 · HTML: https://mlsanity.com/paper/2002.11565/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2020.

## Built on by (most cited first, 30 of 37)

- [Diffusion Models for Adversarial Purification](https://mlsanity.com/paper/2205.07460/) (2022)
- [Adversarial purification with Score-based generative models](https://mlsanity.com/paper/2106.06041/) (2021)
- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [A Dynamical System Perspective for Lipschitz Neural Networks](https://mlsanity.com/paper/2110.12690/) (2021)
- [Attacking Adversarial Attacks as A Defense](https://mlsanity.com/paper/2106.04938/) (2021)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [Mixed Nash Equilibria in the Adversarial Examples Game](https://mlsanity.com/paper/2102.06905/) (2021)
- [Balance, Imbalance, and Rebalance: Understanding Robust Overfitting from a Minimax Game Perspective](https://mlsanity.com/paper/2310.19360/) (2023)
- [The Best Defense is a Good Offense: Adversarial Augmentation against Adversarial Attacks](https://mlsanity.com/paper/2305.14188/) (2023)
- [Towards Consistency in Adversarial Classification](https://mlsanity.com/paper/2205.10022/) (2022)
- [Vulnerabilities in Video Quality Assessment Models: The Challenge of Adversarial Attacks](https://mlsanity.com/paper/2309.13609/) (2023)
- [Building Robust Ensembles via Margin Boosting](https://mlsanity.com/paper/2206.03362/) (2022)
- [Nash Equilibria and Pitfalls of Adversarial Training in Adversarial Robustness Games](https://mlsanity.com/paper/2210.12606/) (2022)
- [The art of defense: letting networks fool the attacker](https://mlsanity.com/paper/2104.02963/) (2021)
- [Game Theoretic Mixed Experts for Combinational Adversarial Machine Learning](https://mlsanity.com/paper/2211.14669/) (2022)
- [Adversarial Training for Defense Against Label Poisoning Attacks](https://mlsanity.com/paper/2502.17121/) (2025)
- [Adversarial Vulnerability of Randomized Ensembles](https://mlsanity.com/paper/2206.06737/) (2022)
- [On the Role of Randomization in Adversarially Robust Classification](https://mlsanity.com/paper/2302.07221/) (2023)
- [Strategic Classification with Randomised Classifiers](https://mlsanity.com/paper/2502.01313/) (2025)
- [When Should You Defend Your Classifier -- A Game-theoretical Analysis of Countermeasures against Adversarial Examples](https://mlsanity.com/paper/2108.07602/) (2021)
- [On the Robustness of Randomized Ensembles to Adversarial Perturbations](https://mlsanity.com/paper/2302.01375/) (2023)
- [Towards Evading the Limits of Randomized Smoothing: A Theoretical Analysis](https://mlsanity.com/paper/2206.01715/) (2022)
- [Metric-Fair Classifier Derandomization](https://mlsanity.com/paper/2206.07826/) (2022)
- [Do we need entire training data for adversarial training?](https://mlsanity.com/paper/2303.06241/) (2023)
- [Adversarial attacks for mixtures of classifiers](https://mlsanity.com/paper/2307.10788/) (2023)
- [Position: Towards Resilience Against Adversarial Examples](https://mlsanity.com/paper/2405.01349/) (2024)
- [Understanding Byzantine Robustness in Federated Learning with A Black-box Server](https://mlsanity.com/paper/2408.06042/) (2024)
- [Robustifying ℓ_∞ Adversarial Training to the Union of Perturbation Models](https://mlsanity.com/paper/2105.14710/) (2021)
- [Scalable Optimal Classifiers for Adversarial Settings under Uncertainty](https://mlsanity.com/paper/2106.14702/) (2021)
- [Achieve Optimal Adversarial Accuracy for Adversarial Deep Learning using Stackelberg Game](https://mlsanity.com/paper/2207.08137/) (2022)

## Abstract (arXiv)

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.