# Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 42 references that are in the map.
- First posted on arXiv 8 Jun 2024.

## Builds on (most cited first, 10 of 10)

- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examples](https://mlsanity.com/paper/2010.03593/) (2020)
- [Fixing Data Augmentation to Improve Adversarial Robustness](https://mlsanity.com/paper/2103.01946/) (2021)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)
- [Adversarially Robust Generalization Just Requires More Unlabeled Data](https://mlsanity.com/paper/1906.00555/) (2019)
- [Adversarial Rademacher Complexity of Deep Neural Networks](https://mlsanity.com/paper/2211.14966/) (2022)
- [Adversarial Risk Bounds via Function Transformation](https://mlsanity.com/paper/1810.09519/) (2018)
- [Adversarial Weight Perturbation Helps Robust Generalization](https://mlsanity.com/paper/2004.05884/) (2020)
- [Adaptive Smoothness-weighted Adversarial Training for Multiple Perturbations with Its Stability Analysis](https://mlsanity.com/paper/2210.00557/) (2022)

## Abstract (arXiv)

Training Deep Neural Networks (DNNs) with adversarial examples often results in poor generalization to test-time adversarial data. This paper investigates this issue, known as adversarially robust generalization, through the lens of Rademacher complexity. Building upon the studies by Khim and Loh (2018); Yin et al. (2019), numerous works have been dedicated to this problem, yet achieving a satisfactory bound remains an elusive goal. Existing works on DNNs either apply to a surrogate loss instead of the robust loss or yield bounds that are notably looser compared to their standard counterparts. In the latter case, the bounds have a higher dependency on the width m of the DNNs or the dimension d of the data, with an extra factor of at least O(√m) or O(√d). This paper presents upper bounds for adversarial Rademacher complexity of DNNs that match the best-known upper bounds in standard settings, as established in the work of Bartlett et al. (2017), with the dependency on width and dimension being O(ln(dm)). The central challenge addressed is calculating the covering number of adversarial function classes. We aim to construct a new cover that possesses two properties: 1) compatibility with adversarial examples, and 2) precision comparable to covers used in standard settings. To this end, we introduce a new variant of covering number called the uniform covering number, specifically designed and proven to reconcile these two properties. Consequently, our method effectively bridges the gap between Rademacher complexity in robust and standard generalization.