# Robustness Implies Generalization via Data-Dependent Generalization Bounds

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

## Key facts

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

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Regularisation of Neural Networks by Enforcing Lipschitz Continuity](https://mlsanity.com/paper/1804.04368/) (2018)
- [Parseval Networks: Improving Robustness to Adversarial Examples](https://mlsanity.com/paper/1704.08847/) (2017)
- [How Does Mixup Help With Robustness and Generalization?](https://mlsanity.com/paper/2010.04819/) (2020)
- [Generalization in Deep Learning](https://mlsanity.com/paper/1710.05468/) (2017)
- [Robust Large Margin Deep Neural Networks](https://mlsanity.com/paper/1605.08254/) (2016)
- [A survey on domain adaptation theory: learning bounds and theoretical guarantees](https://mlsanity.com/paper/2004.11829/) (2020)
- [Orthogonal Deep Neural Networks](https://mlsanity.com/paper/1905.05929/) (2019)
- [When Do Extended Physics-Informed Neural Networks (XPINNs) Improve Generalization?](https://mlsanity.com/paper/2109.09444/) (2021)
- [Generalization Error of Invariant Classifiers](https://mlsanity.com/paper/1610.04574/) (2016)
- [Toward Better Generalization Bounds with Locally Elastic Stability](https://mlsanity.com/paper/2010.13988/) (2020)
- [Discrete-Valued Neural Communication](https://mlsanity.com/paper/2107.02367/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Adversarial Training Helps Transfer Learning via Better Representations](https://mlsanity.com/paper/2106.10189/) (2021)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes](https://mlsanity.com/paper/1908.02419/) (2019)
- [Concentration Inequalities for Multinoulli Random Variables](https://mlsanity.com/paper/2001.11595/) (2020)
- [Multi-View Matrix Completion for Multi-Label Image Classification](https://mlsanity.com/paper/1904.03901/) (2019)
- [Sparse Compositional Metric Learning](https://mlsanity.com/paper/1404.4105/) (2014)

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

- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [Simple Hierarchical Planning with Diffusion](https://mlsanity.com/paper/2401.02644/) (2024)
- [Augmented Physics-Informed Neural Networks (APINNs): A gating network-based soft domain decomposition methodology](https://mlsanity.com/paper/2211.08939/) (2022)
- [An Information-Theoretic Perspective on Variance-Invariance-Covariance Regularization](https://mlsanity.com/paper/2303.00633/) (2023)
- [Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classification](https://mlsanity.com/paper/2301.01597/) (2022)
- [Discrete Key-Value Bottleneck](https://mlsanity.com/paper/2207.11240/) (2022)
- [Last-Layer Fairness Fine-tuning is Simple and Effective for Neural Networks](https://mlsanity.com/paper/2304.03935/) (2023)
- [Can AI Be as Creative as Humans?](https://mlsanity.com/paper/2401.01623/) (2024)
- [On the Lipschitz Constant of Deep Networks and Double Descent](https://mlsanity.com/paper/2301.12309/) (2023)
- [Towards Robust Out-of-Distribution Generalization Bounds via Sharpness](https://mlsanity.com/paper/2403.06392/) (2024)
- [Model-agnostic Measure of Generalization Difficulty](https://mlsanity.com/paper/2305.01034/) (2023)
- [Towards Exact Computation of Inductive Bias](https://mlsanity.com/paper/2406.15941/) (2024)
- [Gentle Local Robustness implies Generalization](https://mlsanity.com/paper/2412.06381/) (2024)
- [Correcting Visual Blur Induced by Attention Distraction to Reduce Hallucinations: Algorithm and Theory](https://mlsanity.com/paper/2605.24602/) (2026)
- [Class-wise Generalization Error: an Information-Theoretic Analysis](https://mlsanity.com/paper/2401.02904/) (2024)
- [Multi-Task Dynamic Pricing in Credit Market with Contextual Information](https://mlsanity.com/paper/2410.14839/) (2024)
- [Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models](https://mlsanity.com/paper/2503.07325/) (2025)
- [Risk-Aware Linear Bandits: Theory and Applications in Smart Order Routing](https://mlsanity.com/paper/2208.02389/) (2022)
- [Generalization of Graph Neural Networks through the Lens of Homomorphism](https://mlsanity.com/paper/2403.06079/) (2024)
- [Bridging Privacy and Robustness for Trustworthy Machine Learning](https://mlsanity.com/paper/2403.16591/) (2024)
- [From Robustness to Improved Generalization and Calibration in Pre-trained Language Models](https://mlsanity.com/paper/2404.00758/) (2024)
- [The Hidden Power of Normalization Layers in Neural Networks: Exponential Capacity Control](https://mlsanity.com/paper/2511.00958/) (2025)
- [Using Synthetic Data to estimate the True Error is theoretically and practically doable](https://mlsanity.com/paper/2511.00964/) (2025)

## Abstract (arXiv)

This paper proves that robustness implies generalization via data-dependent generalization bounds. As a result, robustness and generalization are shown to be connected closely in a data-dependent manner. Our bounds improve previous bounds in two directions, to solve an open problem that has seen little development since 2010. The first is to reduce the dependence on the covering number. The second is to remove the dependence on the hypothesis space. We present several examples, including ones for lasso and deep learning, in which our bounds are provably preferable. The experiments on real-world data and theoretical models demonstrate near-exponential improvements in various situations. To achieve these improvements, we do not require additional assumptions on the unknown distribution; instead, we only incorporate an observable and computable property of the training samples. A key technical innovation is an improved concentration bound for multinomial random variables that is of independent interest beyond robustness and generalization.