# Gentle Local Robustness implies Generalization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 30 references that are in the map.
- First posted on arXiv 9 Dec 2024.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Adversarial Attacks and Defenses in Images, Graphs and Text: A Review](https://mlsanity.com/paper/1909.08072/) (2019)
- [Adversarial Robustness through Local Linearization](https://mlsanity.com/paper/1907.02610/) (2019)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Robust Large Margin Deep Neural Networks](https://mlsanity.com/paper/1605.08254/) (2016)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Orthogonal Deep Neural Networks](https://mlsanity.com/paper/1905.05929/) (2019)
- [Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation](https://mlsanity.com/paper/1905.03684/) (2019)
- [Generalization Error of Invariant Classifiers](https://mlsanity.com/paper/1610.04574/) (2016)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Robustness Implies Generalization via Data-Dependent Generalization Bounds](https://mlsanity.com/paper/2206.13497/) (2022)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [Instance-Dependent Generalization Bounds via Optimal Transport](https://mlsanity.com/paper/2211.01258/) (2022)
- [Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty](https://mlsanity.com/paper/2210.11289/) (2022)
- [Sparse Compositional Metric Learning](https://mlsanity.com/paper/1404.4105/) (2014)

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

- [Provably Improving Generalization of Few-Shot Models with Synthetic Data](https://mlsanity.com/paper/2505.24190/) (2025)
- [Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models](https://mlsanity.com/paper/2503.07325/) (2025)
- [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)

Robustness and generalization ability of machine learning models are of utmost importance in various application domains. There is a wide interest in efficient ways to analyze those properties. One important direction is to analyze connection between those two properties. Prior theories suggest that a robust learning algorithm can produce trained models with a high generalization ability. However, we show in this work that the existing error bounds are vacuous for the Bayes optimal classifier which is the best among all measurable classifiers for a classification problem with overlapping classes. Those bounds cannot converge to the true error of this ideal classifier. This is undesirable, surprizing, and never known before. We then present a class of novel bounds, which are model-dependent and provably tighter than the existing robustness-based ones. Unlike prior ones, our bounds are guaranteed to converge to the true error of the best classifier, as the number of samples increases. We further provide an extensive experiment and find that two of our bounds are often non-vacuous for a large class of deep neural networks, pretrained from ImageNet.