mlsanityData to 7 Oct 2026

Adversarial Rademacher Complexity of Deep Neural Networks

arXiv 2211.14966 ↗First posted 27 Nov 2022cs.LGcited by 18

Not on the map. Why?

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.

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

Builds on

44 of 70 references.

References · 44

  1. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,267
  2. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  3. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  4. 2013Intriguing properties of neural networkscited by 5,114
  5. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  6. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  7. 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
  8. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  9. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  10. 2017Exploring Generalization in Deep Learningcited by 595
  11. 2020On Adaptive Attacks to Adversarial Example Defensescited by 547
  12. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
32 more
  1. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  2. 2018Adversarially Robust Generalization Requires More Datacited by 318
  3. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  4. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  5. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  6. 2018Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionalitycited by 280
  7. 2020Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examplescited by 275
  8. 2017PixelDefend: Leveraging Generative Models to Understand and Defend against Adversarial Examplescited by 243
  9. 2017Improving the Adversarial Robustness and Interpretability of Deep Neural Networks by Regularizing their Input Gradientscited by 236
  10. 2021Fixing Data Augmentation to Improve Adversarial Robustnesscited by 201
  11. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  12. 2019Adversarial Training Can Hurt Generalizationcited by 131
  13. 2020Feature Purification: How Adversarial Training Performs Robust Deep Learningcited by 107
  14. 2018Improving DNN Robustness to Adversarial Attacks using Jacobian Regularizationcited by 88
  15. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  16. 2020Precise Tradeoffs in Adversarial Training for Linear Regressioncited by 76
  17. 2019Adversarially Robust Generalization Just Requires More Unlabeled Datacited by 75
  18. 2019Distributionally Robust Optimization: A Reviewcited by 75
  19. 2018Generalizable Adversarial Training via Spectral Normalizationcited by 68
  20. 2020Adversarial Learning Guarantees for Linear Hypotheses and Neural Networkscited by 47
  21. 2019Scaleable input gradient regularization for adversarial robustnesscited by 45
  22. 2018On the Geometry of Adversarial Examplescited by 43
  23. 2022Stability Analysis and Generalization Bounds of Adversarial Trainingcited by 30
  24. 2018PAC-learning in the presence of evasion adversariescited by 23
  25. 2020On the Generalization Properties of Adversarial Trainingcited by 23
  26. 2018Improved Generalization Bounds for Adversarially Robust Learningcited by 22
  27. 2020Adversarially Robust Estimate and Risk Analysis in Linear Regressioncited by 22
  28. 2020On the Rademacher Complexity of Linear Hypothesis Setscited by 17
  29. 2020Asymptotic Behavior of Adversarial Training in Binary Classificationcited by 14
  30. 2018Interpreting Adversarial Robustness: A View from Decision Surface in Input Spacecited by 10
  31. 2022Adaptive Smoothness-weighted Adversarial Training for Multiple Perturbations with Its Stability Analysiscited by 9
  32. 2022Unlabeled Data Help: Minimax Analysis and Adversarial Robustnesscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 9; 2025: 4; 2026: 2.

18 papers.

Sort:

  1. 2023PAC-Bayesian Spectrally-Normalized Bounds for Adversarially Robust Generalizationcited by 9
  2. 2024Stability and Generalization in Free Adversarial Trainingcited by 5
  3. 2023Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networkscited by 4
  4. 2024PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Networkcited by 4
  5. 2024The Art of Deception: Robust Backdoor Attack using Dynamic Stacking of Triggerscited by 3
  6. 2024Adversarial Quantum Machine Learning: An Information-Theoretic Generalization Analysiscited by 3
  7. 2024Uniformly Stable Algorithms for Adversarial Training and Beyondcited by 2
  8. 2024Regularization for Adversarial Robust Learningcited by 2
  9. 2025Impact of Positional Encoding: Clean and Adversarial Rademacher Complexity for Transformers under In-Context Regressioncited by 2
  10. 2023Adversarial Training with Generated Data in High-Dimensional Regression: An Asymptotic Studycited by 1
  11. 2024Can overfitted deep neural networks in adversarial training generalize? -- An approximation viewpointcited by 1
  12. 2025On the Generalization of Adversarially Trained Quantum Classifierscited by 1
6 more
  1. 2025PRBench: A Standardized Probabilistic Robustness Benchmarkcited by 1
  2. 2026Explanation-Guided Adversarial Training for Robust and Interpretable Modelscited by 1
  3. 2024Better Representations via Adversarial Training in Pre-Training: A Theoretical Perspectivecited by 0
  4. 2024Bridging the Gap: Rademacher Complexity in Robust and Standard Generalizationcited by 0
  5. 2025SG-OIF: A Stability-Guided Online Influence Framework for Reliable Vision Datacited by 0
  6. 2026A Rigorous, Tractable Measure of Model Complexitycited by 0