# Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2020.

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [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)
- [Stability Analysis and Generalization Bounds of Adversarial Training](https://mlsanity.com/paper/2210.00960/) (2022)
- [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)
- [Understanding the Generalization Benefit of Model Invariance from a Data Perspective](https://mlsanity.com/paper/2111.05529/) (2021)
- [Adversarial Rademacher Complexity of Deep Neural Networks](https://mlsanity.com/paper/2211.14966/) (2022)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)
- [Understanding Adversarial Robustness Against On-manifold Adversarial Examples](https://mlsanity.com/paper/2210.00430/) (2022)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [Outlier Robust Adversarial Training](https://mlsanity.com/paper/2309.05145/) (2023)
- [The Blessing and Curse of Dimensionality in Safety Alignment](https://mlsanity.com/paper/2507.20333/) (2025)
- [On the robustness of randomized classifiers to adversarial examples](https://mlsanity.com/paper/2102.10875/) (2021)
- [On the Role of Generalization in Transferability of Adversarial Examples](https://mlsanity.com/paper/2206.09238/) (2022)
- [Adaptive Smoothness-weighted Adversarial Training for Multiple Perturbations with Its Stability Analysis](https://mlsanity.com/paper/2210.00557/) (2022)
- [PAC-Bayesian Spectrally-Normalized Bounds for Adversarially Robust Generalization](https://mlsanity.com/paper/2310.06182/) (2023)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [Generalization Bounds for Adversarial Contrastive Learning](https://mlsanity.com/paper/2302.10633/) (2023)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [Stability and Generalization in Free Adversarial Training](https://mlsanity.com/paper/2404.08980/) (2024)
- [The Price of Implicit Bias in Adversarially Robust Generalization](https://mlsanity.com/paper/2406.04981/) (2024)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [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)
- [On the Geometry of Regularization in Adversarial Training: High-Dimensional Asymptotics and Generalization Bounds](https://mlsanity.com/paper/2410.16073/) (2024)
- [How Does Adversarial Fine-Tuning Benefit BERT?](https://mlsanity.com/paper/2108.13602/) (2021)
- [The Consistency of Adversarial Training for Binary Classification](https://mlsanity.com/paper/2206.09099/) (2022)
- [Adversarial Quantum Machine Learning: An Information-Theoretic Generalization Analysis](https://mlsanity.com/paper/2402.00176/) (2024)
- [Wasserstein Distributionally Robust Nonparametric Regression](https://mlsanity.com/paper/2505.07967/) (2025)

## Abstract (arXiv)

Adversarial or test time robustness measures the susceptibility of a classifier to perturbations to the test input. While there has been a flurry of recent work on designing defenses against such perturbations, the theory of adversarial robustness is not well understood. In order to make progress on this, we focus on the problem of understanding generalization in adversarial settings, via the lens of Rademacher complexity. We give upper and lower bounds for the adversarial empirical Rademacher complexity of linear hypotheses with adversarial perturbations measured in lr-norm for an arbitrary r ≥ 1. This generalizes the recent result of [Yin et al.'19] that studies the case of r = ∞, and provides a finer analysis of the dependence on the input dimensionality as compared to the recent work of [Khim and Loh'19] on linear hypothesis classes. We then extend our analysis to provide Rademacher complexity lower and upper bounds for a single ReLU unit. Finally, we give adversarial Rademacher complexity bounds for feed-forward neural networks with one hidden layer. Unlike previous works we directly provide bounds on the adversarial Rademacher complexity of the given network, as opposed to a bound on a surrogate. A by-product of our analysis also leads to tighter bounds for the Rademacher complexity of linear hypotheses, for which we give a detailed analysis and present a comparison with existing bounds.