# Adversarial Rademacher Complexity of Deep Neural Networks

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 70 references that are in the map.
- First posted on arXiv 27 Nov 2022.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [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)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [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)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionality](https://mlsanity.com/paper/1801.02613/) (2018)
- [Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examples](https://mlsanity.com/paper/2010.03593/) (2020)
- [PixelDefend: Leveraging Generative Models to Understand and Defend against Adversarial Examples](https://mlsanity.com/paper/1710.10766/) (2017)
- [Improving the Adversarial Robustness and Interpretability of Deep Neural Networks by Regularizing their Input Gradients](https://mlsanity.com/paper/1711.09404/) (2017)
- [Fixing Data Augmentation to Improve Adversarial Robustness](https://mlsanity.com/paper/2103.01946/) (2021)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)
- [Feature Purification: How Adversarial Training Performs Robust Deep Learning](https://mlsanity.com/paper/2005.10190/) (2020)
- [Improving DNN Robustness to Adversarial Attacks using Jacobian Regularization](https://mlsanity.com/paper/1803.08680/) (2018)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Precise Tradeoffs in Adversarial Training for Linear Regression](https://mlsanity.com/paper/2002.10477/) (2020)
- [Adversarially Robust Generalization Just Requires More Unlabeled Data](https://mlsanity.com/paper/1906.00555/) (2019)
- [Distributionally Robust Optimization: A Review](https://mlsanity.com/paper/1908.05659/) (2019)

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

- [PAC-Bayesian Spectrally-Normalized Bounds for Adversarially Robust Generalization](https://mlsanity.com/paper/2310.06182/) (2023)
- [Stability and Generalization in Free Adversarial Training](https://mlsanity.com/paper/2404.08980/) (2024)
- [Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks](https://mlsanity.com/paper/2303.00196/) (2023)
- [PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Network](https://mlsanity.com/paper/2402.04038/) (2024)
- [The Art of Deception: Robust Backdoor Attack using Dynamic Stacking of Triggers](https://mlsanity.com/paper/2401.01537/) (2024)
- [Adversarial Quantum Machine Learning: An Information-Theoretic Generalization Analysis](https://mlsanity.com/paper/2402.00176/) (2024)
- [Regularization for Adversarial Robust Learning](https://mlsanity.com/paper/2408.09672/) (2024)
- [Uniformly Stable Algorithms for Adversarial Training and Beyond](https://mlsanity.com/paper/2405.01817/) (2024)
- [Impact of Positional Encoding: Clean and Adversarial Rademacher Complexity for Transformers under In-Context Regression](https://mlsanity.com/paper/2512.09275/) (2025)
- [Adversarial Training with Generated Data in High-Dimensional Regression: An Asymptotic Study](https://mlsanity.com/paper/2306.12582/) (2023)
- [Can overfitted deep neural networks in adversarial training generalize? -- An approximation viewpoint](https://mlsanity.com/paper/2401.13624/) (2024)
- [On the Generalization of Adversarially Trained Quantum Classifiers](https://mlsanity.com/paper/2504.17690/) (2025)
- [PRBench: A Standardized Probabilistic Robustness Benchmark](https://mlsanity.com/paper/2511.01724/) (2025)
- [Explanation-Guided Adversarial Training for Robust and Interpretable Models](https://mlsanity.com/paper/2603.01938/) (2026)
- [Better Representations via Adversarial Training in Pre-Training: A Theoretical Perspective](https://mlsanity.com/paper/2401.15248/) (2024)
- [Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization](https://mlsanity.com/paper/2406.05372/) (2024)
- [SG-OIF: A Stability-Guided Online Influence Framework for Reliable Vision Data](https://mlsanity.com/paper/2511.19466/) (2025)
- [A Rigorous, Tractable Measure of Model Complexity](https://mlsanity.com/paper/2605.21167/) (2026)

## Abstract (arXiv)

Deep neural networks (DNNs) are highly vulnerable to adversarial attacks. Ideally, a robust model should perform well on both perturbed training data and unseen perturbed test data. While DNNs can fit perturbed training data, generalizing to perturbed test data remains a significant challenge. This motivates the study of generalization guarantees from a learning theory perspective. This paper focuses on adversarial Rademacher complexity (ARC), first introduced by Khim and Loh (2018) and Yin et al. (2019). Their work primarily addressed linear functions and highlighted the open question of how to bound ARC for neural networks. Since then, several attempts have been made, with the latest results applying ARC only to two-layer neural networks. The main challenge arises from the dynamic nature and unknown closed-form solution of adversarial examples. In this paper, we resolve this issue and provide the first bound on ARC for deep neural networks. Our bound is qualitatively comparable to Rademacher complexity bounds in similar settings. The key ingredient is a new concept we introduce, termed intermediate adversarial examples, along with a framework for calculating the covering number that is compatible with them. Finally, we present experiments to analyze poor robust generalization, demonstrating that the weight norm is a crucial factor influencing the robust generalization gap.