# Fantastic Generalization Measures are Nowhere to be Found

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 42 references that are in the map.
- First posted on arXiv 24 Sep 2023.

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

- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Path-SGD: Path-Normalized Optimization in Deep Neural Networks](https://mlsanity.com/paper/1506.02617/) (2015)
- [Fisher-Rao Metric, Geometry, and Complexity of Neural Networks](https://mlsanity.com/paper/1711.01530/) (2017)
- [In Search of Robust Measures of Generalization](https://mlsanity.com/paper/2010.11924/) (2020)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [Generalization in Deep Networks: The Role of Distance from Initialization](https://mlsanity.com/paper/1901.01672/) (2019)
- [Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience](https://mlsanity.com/paper/1905.13344/) (2019)
- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [A New Family of Generalization Bounds Using Samplewise Evaluated CMI](https://mlsanity.com/paper/2210.06422/) (2022)
- [Failures of model-dependent generalization bounds for least-norm interpolation](https://mlsanity.com/paper/2010.08479/) (2020)
- [Tighter Information-Theoretic Generalization Bounds from Supersamples](https://mlsanity.com/paper/2302.02432/) (2023)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [On Symmetry and Initialization for Neural Networks](https://mlsanity.com/paper/1907.00560/) (2019)

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

- [A PAC-Bayesian Link Between Generalisation and Flat Minima](https://mlsanity.com/paper/2402.08508/) (2024)
- [The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms](https://mlsanity.com/paper/2411.12030/) (2024)
- [Approximating Metric Magnitude of Point Sets](https://mlsanity.com/paper/2409.04411/) (2024)
- [Hallmarks of Optimization Trajectories in Neural Networks: Directional Exploration and Redundancy](https://mlsanity.com/paper/2403.07379/) (2024)
- [Which Algorithms Have Tight Generalization Bounds?](https://mlsanity.com/paper/2410.01969/) (2024)
- [How Ensembles of Distilled Policies Improve Generalisation in Reinforcement Learning](https://mlsanity.com/paper/2505.16581/) (2025)
- [Flatness After All?](https://mlsanity.com/paper/2506.17809/) (2025)
- [Failure Modes for Deep Learning-Based Online Mapping: How to Measure and Address Them](https://mlsanity.com/paper/2603.19852/) (2026)
- [Generalization Measures for Zero-Shot Cross-Lingual Transfer](https://mlsanity.com/paper/2404.15928/) (2024)
- [On Uniform, Bayesian, and PAC-Bayesian Deep Ensembles](https://mlsanity.com/paper/2406.05469/) (2024)
- [Position: Many generalization measures for deep learning are fragile](https://mlsanity.com/paper/2510.18934/) (2025)
- [Takeuchi's Information Criteria as Generalization Measures for DNNs Close to NTK Regime](https://mlsanity.com/paper/2602.23219/) (2026)
- [Benefits of Low-Cost Bio-Inspiration in the Age of Overparametrization](https://mlsanity.com/paper/2604.20365/) (2026)
- [Minimax Limits of k-Fold Cross-Validation via Majority](https://mlsanity.com/paper/2605.25859/) (2026)
- [Generalization in offline RL: The structure is more important than the amount of pessimism](https://mlsanity.com/paper/2607.02288/) (2026)
- [Across the Loss Landscape with Progressive Growth](https://mlsanity.com/paper/2608.24568/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)
- [A Generalisation Signal Need Not Be a Model-Selection Signal](https://mlsanity.com/paper/2609.39099/) (2026)
- [Target-Dependent Limits of Causal Repair: A Leading-Log Frontier in a Gaussian Model](https://mlsanity.com/paper/2610.00424/) (2026)

## Abstract (arXiv)

We study the notion of a generalization bound being uniformly tight, meaning that the difference between the bound and the population loss is small for all learning algorithms and all population distributions. Numerous generalization bounds have been proposed in the literature as potential explanations for the ability of neural networks to generalize in the overparameterized setting. However, in their paper ``Fantastic Generalization Measures and Where to Find Them,'' Jiang et al. (2020) examine more than a dozen generalization bounds, and show empirically that none of them are uniformly tight. This raises the question of whether uniformly-tight generalization bounds are at all possible in the overparameterized setting. We consider two types of generalization bounds: (1) bounds that may depend on the training set and the learned hypothesis (e.g., margin bounds). We prove mathematically that no such bound can be uniformly tight in the overparameterized setting; (2) bounds that may in addition also depend on the learning algorithm (e.g., stability bounds). For these bounds, we show a trade-off between the algorithm's performance and the bound's tightness. Namely, if the algorithm achieves good accuracy on certain distributions, then no generalization bound can be uniformly tight for it in the overparameterized setting. We explain how these formal results can, in our view, inform research on generalization bounds for neural networks, while stressing that other interpretations of these results are also possible.