# Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 84 references that are in the map.
- First posted on arXiv 27 May 2022.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [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)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Adversarial Training for Free!](https://mlsanity.com/paper/1904.12843/) (2019)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Overfitting in adversarially robust deep learning](https://mlsanity.com/paper/2002.11569/) (2020)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Relative Flatness and Generalization](https://mlsanity.com/paper/2001.00939/) (2020)
- [Why Deep Neural Networks for Function Approximation?](https://mlsanity.com/paper/1610.04161/) (2016)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Provable approximation properties for deep neural networks](https://mlsanity.com/paper/1509.07385/) (2015)
- [Convergence of Adversarial Training in Overparametrized Neural Networks](https://mlsanity.com/paper/1906.07916/) (2019)
- [On the Intrinsic Dimensionality of Image Representations](https://mlsanity.com/paper/1803.09672/) (2018)

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

- [Deep Networks Always Grok and Here is Why](https://mlsanity.com/paper/2402.15555/) (2024)
- [On the Importance of Backbone to the Adversarial Robustness of Object Detectors](https://mlsanity.com/paper/2305.17438/) (2023)
- [Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data](https://mlsanity.com/paper/2410.08503/) (2024)
- [Understanding CNN Fragility When Learning With Imbalanced Data](https://mlsanity.com/paper/2210.09465/) (2022)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [On the Local Complexity of Linear Regions in Deep ReLU Networks](https://mlsanity.com/paper/2412.18283/) (2024)
- [On the Clean Generalization and Robust Overfitting in Adversarial Training from Two Theoretical Views: Representation Complexity and Training Dynamics](https://mlsanity.com/paper/2306.01271/) (2023)
- [Data-Dependent Stability Analysis of Adversarial Training](https://mlsanity.com/paper/2401.03156/) (2024)
- [A direct proof of a unified law of robustness for Bregman divergence losses](https://mlsanity.com/paper/2405.16639/) (2024)
- [Intriguing Properties of Robust Classification](https://mlsanity.com/paper/2412.04245/) (2024)
- [Over-parameterization and Adversarial Robustness in Neural Networks: An Overview and Empirical Analysis](https://mlsanity.com/paper/2406.10090/) (2024)
- [To Measure or Not: A Cost-Sensitive, Selective Measuring Environment for Agricultural Management Decisions with Reinforcement Learning](https://mlsanity.com/paper/2501.12823/) (2025)
- [Reward Sharpness-Aware Fine-Tuning for Diffusion Models](https://mlsanity.com/paper/2603.21175/) (2026)
- [Can overfitted deep neural networks in adversarial training generalize? -- An approximation viewpoint](https://mlsanity.com/paper/2401.13624/) (2024)
- [Is Adversarial Training with Compressed Datasets Effective?](https://mlsanity.com/paper/2402.05675/) (2024)
- [From Robustness to Improved Generalization and Calibration in Pre-trained Language Models](https://mlsanity.com/paper/2404.00758/) (2024)
- [A practical generalization metric for deep networks benchmarking](https://mlsanity.com/paper/2409.01498/) (2024)
- [Generalizability of Memorization Neural Networks](https://mlsanity.com/paper/2411.00372/) (2024)
- [Curse of Dimensionality in Neural Network Optimization](https://mlsanity.com/paper/2502.05360/) (2025)
- [Analyzing the Power of Chain of Thought through Memorization Capabilities](https://mlsanity.com/paper/2511.01190/) (2025)
- [Does Order Matter : Connecting The Law of Robustness to Robust Generalization](https://mlsanity.com/paper/2602.20971/) (2026)
- [Towards White Box Deep Learning](https://mlsanity.com/paper/2403.09863/) (2024)
- [Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Ability](https://mlsanity.com/paper/2503.04111/) (2025)

## Abstract (arXiv)

It is well-known that modern neural networks are vulnerable to adversarial examples. To mitigate this problem, a series of robust learning algorithms have been proposed. However, although the robust training error can be near zero via some methods, all existing algorithms lead to a high robust generalization error. In this paper, we provide a theoretical understanding of this puzzling phenomenon from the perspective of expressive power for deep neural networks. Specifically, for binary classification problems with well-separated data, we show that, for ReLU networks, while mild over-parameterization is sufficient for high robust training accuracy, there exists a constant robust generalization gap unless the size of the neural network is exponential in the data dimension d. This result holds even if the data is linear separable (which means achieving standard generalization is easy), and more generally for any parameterized function classes as long as their VC dimension is at most polynomial in the number of parameters. Moreover, we establish an improved upper bound of exp(O(k)) for the network size to achieve low robust generalization error when the data lies on a manifold with intrinsic dimension k (k ll d). Nonetheless, we also have a lower bound that grows exponentially with respect to k -- the curse of dimensionality is inevitable. By demonstrating an exponential separation between the network size for achieving low robust training and generalization error, our results reveal that the hardness of robust generalization may stem from the expressive power of practical models.