# A Survey on Data-Dependent Worst-Case Generalization Bounds

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 17 references that are in the map.
- First posted on arXiv 13 May 2026.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [PAC-Bayes Analysis Beyond the Usual Bounds](https://mlsanity.com/paper/2006.13057/) (2020)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [Generalization Bounds with Data-dependent Fractal Dimensions](https://mlsanity.com/paper/2302.02766/) (2023)
- [Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms](https://mlsanity.com/paper/2407.08723/) (2024)
- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (2024)
- [Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds](https://mlsanity.com/paper/2507.06775/) (2025)

## Abstract (arXiv)

Deep neural networks generalize well despite being heavily overparameterized, in apparent contradiction with classical learning theory based on uniform convergence over fixed hypothesis spaces. Uniform bounds over the entire parameter space are vacuous in this regime, and recent work has shown that non-vacuous guarantees can be recovered by restricting attention to the part of parameter space that the algorithm actually visits. This survey paper organizes this line of work around three steps: extending PAC-Bayesian theory to random, data-dependent hypothesis sets (arXiv:2404.17442); refining the complexity term with geometric and topological descriptors of the optimization trajectory, including fractal dimensions, alpha-weighted lifetime sums, and positive magnitude (arXiv:2006.09313, arXiv:2302.02766, arXiv:2407.08723); and replacing the resulting information-theoretic terms by stability assumptions (arXiv:2507.06775). We unify these contributions around a single template inequality and a head-to-head comparison of the resulting bounds.