mlsanityData to 14 Oct 2026

Robustness Implies Generalization via Data-Dependent Generalization Bounds

arXiv 2206.13497 ↗First posted 27 Jun 2022cs.LG cs.AI cs.CVcited by 23

Not on the map. Why?

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.

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

21 of 58 references.

References · 21

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  2. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  3. 2018Deep Learning for Classical Japanese Literaturecited by 422
  4. 2018Regularisation of Neural Networks by Enforcing Lipschitz Continuitycited by 314
  5. 2017Parseval Networks: Improving Robustness to Adversarial Examplescited by 293
  6. 2020How Does Mixup Help With Robustness and Generalization?cited by 193
  7. 2017Generalization in Deep Learningcited by 146
  8. 2016Robust Large Margin Deep Neural Networkscited by 118
  9. 2020A survey on domain adaptation theory: learning bounds and theoretical guaranteescited by 109
  10. 2019Orthogonal Deep Neural Networkscited by 72
  11. 2021When Do Extended Physics-Informed Neural Networks (XPINNs) Improve Generalization?cited by 58
  12. 2016Generalization Error of Invariant Classifierscited by 42
9 more
  1. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 42
  2. 2021Discrete-Valued Neural Communicationcited by 39
  3. 2021Adversarial Robustness with Semi-Infinite Constrained Learningcited by 39
  4. 2021Adversarial Training Helps Transfer Learning via Better Representationscited by 36
  5. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 29
  6. 2019Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizescited by 29
  7. 2020Concentration Inequalities for Multinoulli Random Variablescited by 12
  8. 2019Multi-View Matrix Completion for Multi-Label Image Classificationcited by 6
  9. 2014Sparse Compositional Metric Learningcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 5; 2024: 10; 2025: 3; 2026: 1.

23 papers.

Sort:

By area:

  1. 2023How Does Information Bottleneck Help Deep Learning?cited by 93
  2. 2024Simple Hierarchical Planning with Diffusioncited by 73
  3. 2022Augmented Physics-Informed Neural Networks (APINNs): A gating network-based soft domain decomposition methodologycited by 44
  4. 2023An Information-Theoretic Perspective on Variance-Invariance-Covariance Regularizationcited by 25
  5. 2022Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classificationcited by 20
  6. 2022Discrete Key-Value Bottleneckcited by 18
  7. 2023Last-Layer Fairness Fine-tuning is Simple and Effective for Neural Networkscited by 17
  8. 2024Can AI Be as Creative as Humans?cited by 17
  9. 2023On the Lipschitz Constant of Deep Networks and Double Descentcited by 11
  10. 2024Towards Robust Out-of-Distribution Generalization Bounds via Sharpnesscited by 11
  11. 2023Model-agnostic Measure of Generalization Difficultycited by 7
  12. 2024Towards Exact Computation of Inductive Biascited by 5
11 more
  1. 2024Gentle Local Robustness implies Generalizationcited by 4
  2. 2026Correcting Visual Blur Induced by Attention Distraction to Reduce Hallucinations: Algorithm and Theorycited by 3
  3. 2024Class-wise Generalization Error: an Information-Theoretic Analysiscited by 2
  4. 2024Multi-Task Dynamic Pricing in Credit Market with Contextual Informationcited by 2
  5. 2025Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained modelscited by 2
  6. 2022Risk-Aware Linear Bandits: Theory and Applications in Smart Order Routingcited by 1
  7. 2024Generalization of Graph Neural Networks through the Lens of Homomorphismcited by 1
  8. 2024Bridging Privacy and Robustness for Trustworthy Machine Learningcited by 1
  9. 2024From Robustness to Improved Generalization and Calibration in Pre-trained Language Modelscited by 1
  10. 2025The Hidden Power of Normalization Layers in Neural Networks: Exponential Capacity Controlcited by 0
  11. 2025Using Synthetic Data to estimate the True Error is theoretically and practically doablecited by 0