# Rademacher Complexity for Adversarially Robust Generalization

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

## Key facts

- Cited by 132 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2018.

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

- [Recent Advances in Adversarial Training for Adversarial Robustness](https://mlsanity.com/paper/2102.01356/) (2021)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Adversarial Unlearning of Backdoors via Implicit Hypergradient](https://mlsanity.com/paper/2110.03735/) (2021)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Improved OOD Generalization via Adversarial Training and Pre-training](https://mlsanity.com/paper/2105.11144/) (2021)
- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (2021)
- [Exploring Memorization in Adversarial Training](https://mlsanity.com/paper/2106.01606/) (2021)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [On the Power of Foundation Models](https://mlsanity.com/paper/2211.16327/) (2022)
- [Adaptive Retrieval Without Self-Knowledge? Bringing Uncertainty Back Home](https://mlsanity.com/paper/2501.12835/) (2025)
- [Stability Analysis and Generalization Bounds of Adversarial Training](https://mlsanity.com/paper/2210.00960/) (2022)
- [WAT: Improve the Worst-class Robustness in Adversarial Training](https://mlsanity.com/paper/2302.04025/) (2023)
- [Understanding Generalization of Federated Learning via Stability: Heterogeneity Matters](https://mlsanity.com/paper/2306.03824/) (2023)
- [A Finer Calibration Analysis for Adversarial Robustness](https://mlsanity.com/paper/2105.01550/) (2021)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [Exploring the Relationship between Architecture and Adversarially Robust Generalization](https://mlsanity.com/paper/2209.14105/) (2022)
- [Formalizing Generalization and Robustness of Neural Networks to Weight Perturbations](https://mlsanity.com/paper/2103.02200/) (2021)
- [Understanding the Generalization Benefit of Model Invariance from a Data Perspective](https://mlsanity.com/paper/2111.05529/) (2021)
- [Overparameterized Linear Regression under Adversarial Attacks](https://mlsanity.com/paper/2204.06274/) (2022)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [Adversarial Rademacher Complexity of Deep Neural Networks](https://mlsanity.com/paper/2211.14966/) (2022)
- [Demystifying Causal Features on Adversarial Examples and Causal Inoculation for Robust Network by Adversarial Instrumental Variable Regression](https://mlsanity.com/paper/2303.01052/) (2023)
- [Regularization properties of adversarially-trained linear regression](https://mlsanity.com/paper/2310.10807/) (2023)
- [What is a Good Metric to Study Generalization of Minimax Learners?](https://mlsanity.com/paper/2206.04502/) (2022)
- [Out-of-Distribution Generalization in Time Series: A Survey](https://mlsanity.com/paper/2503.13868/) (2025)
- [Effective dimension of machine learning models](https://mlsanity.com/paper/2112.04807/) (2021)
- [Why adversarial training can hurt robust accuracy](https://mlsanity.com/paper/2203.02006/) (2022)
- [A PAC-Bayes Analysis of Adversarial Robustness](https://mlsanity.com/paper/2102.11069/) (2021)

## Abstract (arXiv)

Many machine learning models are vulnerable to adversarial attacks; for example, adding adversarial perturbations that are imperceptible to humans can often make machine learning models produce wrong predictions with high confidence. Moreover, although we may obtain robust models on the training dataset via adversarial training, in some problems the learned models cannot generalize well to the test data. In this paper, we focus on ℓ_∞ attacks, and study the adversarially robust generalization problem through the lens of Rademacher complexity. For binary linear classifiers, we prove tight bounds for the adversarial Rademacher complexity, and show that the adversarial Rademacher complexity is never smaller than its natural counterpart, and it has an unavoidable dimension dependence, unless the weight vector has bounded ℓ1 norm. The results also extend to multi-class linear classifiers. For (nonlinear) neural networks, we show that the dimension dependence in the adversarial Rademacher complexity also exists. We further consider a surrogate adversarial loss for one-hidden layer ReLU network and prove margin bounds for this setting. Our results indicate that having ℓ1 norm constraints on the weight matrices might be a potential way to improve generalization in the adversarial setting. We demonstrate experimental results that validate our theoretical findings.