# On the robustness of randomized classifiers to adversarial examples

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 76 references that are in the map.
- First posted on arXiv 22 Feb 2021.

## Builds on (most cited first, 30 of 38)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks](https://mlsanity.com/paper/2003.01690/) (2020)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Mitigating Adversarial Effects Through Randomization](https://mlsanity.com/paper/1711.01991/) (2017)
- [The Effectiveness of Data Augmentation in Image Classification using Deep Learning](https://mlsanity.com/paper/1712.04621/) (2017)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [On Detecting Adversarial Perturbations](https://mlsanity.com/paper/1702.04267/) (2017)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [Stochastic Activation Pruning for Robust Adversarial Defense](https://mlsanity.com/paper/1803.01442/) (2018)
- [Towards Robust Neural Networks via Random Self-ensemble](https://mlsanity.com/paper/1712.00673/) (2017)
- [EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examples](https://mlsanity.com/paper/1709.04114/) (2017)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Is Robustness the Cost of Accuracy? -- A Comprehensive Study on the Robustness of 18 Deep Image Classification Models](https://mlsanity.com/paper/1808.01688/) (2018)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Parametric Noise Injection: Trainable Randomness to Improve Deep Neural Network Robustness against Adversarial Attack](https://mlsanity.com/paper/1811.09310/) (2018)
- [Deep Learning with Gaussian Differential Privacy](https://mlsanity.com/paper/1911.11607/) (2019)
- [Relative Flatness and Generalization](https://mlsanity.com/paper/2001.00939/) (2020)

## Built on by (most cited first, 9 of 9)

- [Noisy Feature Mixup](https://mlsanity.com/paper/2110.02180/) (2021)
- [On the Limitations of Stochastic Pre-processing Defenses](https://mlsanity.com/paper/2206.09491/) (2022)
- [Implementing Responsible AI: Tensions and Trade-Offs Between Ethics Aspects](https://mlsanity.com/paper/2304.08275/) (2023)
- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Certifying Model Accuracy under Distribution Shifts](https://mlsanity.com/paper/2201.12440/) (2022)
- [On the Role of Randomization in Adversarially Robust Classification](https://mlsanity.com/paper/2302.07221/) (2023)
- [Adversarial attacks for mixtures of classifiers](https://mlsanity.com/paper/2307.10788/) (2023)
- [SoK: Analyzing Adversarial Examples: A Framework to Study Adversary Knowledge](https://mlsanity.com/paper/2402.14937/) (2024)
- [Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory](https://mlsanity.com/paper/2503.14299/) (2025)

## Abstract (arXiv)

This paper investigates the theory of robustness against adversarial attacks. We focus on randomized classifiers (i.e. classifiers that output random variables) and provide a thorough analysis of their behavior through the lens of statistical learning theory and information theory. To this aim, we introduce a new notion of robustness for randomized classifiers, enforcing local Lipschitzness using probability metrics. Equipped with this definition, we make two new contributions. The first one consists in devising a new upper bound on the adversarial generalization gap of randomized classifiers. More precisely, we devise bounds on the generalization gap and the adversarial gap (i.e. the gap between the risk and the worst-case risk under attack) of randomized classifiers. The second contribution presents a yet simple but efficient noise injection method to design robust randomized classifiers. We show that our results are applicable to a wide range of machine learning models under mild hypotheses. We further corroborate our findings with experimental results using deep neural networks on standard image datasets, namely CIFAR-10 and CIFAR-100. All robust models we trained models can simultaneously achieve state-of-the-art accuracy (over 0.82 clean accuracy on CIFAR-10) and enjoy guaranteed robust accuracy bounds (0.45 against ℓ2 adversaries with magnitude 0.5 on CIFAR-10).