# Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 69 references that are in the map.
- First posted on arXiv 26 Apr 2024.

## Builds on (most cited first, 30 of 34)

- [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)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [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)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [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)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)
- [Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm](https://mlsanity.com/paper/1503.08329/) (2015)
- [A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent](https://mlsanity.com/paper/1709.06617/) (2017)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [Time-independent Generalization Bounds for SGLD in Non-convex Settings](https://mlsanity.com/paper/2111.12876/) (2021)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [Hypothesis Set Stability and Generalization](https://mlsanity.com/paper/1904.04755/) (2019)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [A General Framework for the Practical Disintegration of PAC-Bayesian Bounds](https://mlsanity.com/paper/2102.08649/) (2021)
- [On the Rademacher Complexity of Linear Hypothesis Sets](https://mlsanity.com/paper/2007.11045/) (2020)
- [Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound](https://mlsanity.com/paper/2106.12535/) (2021)

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

- [Epistemic Artificial Intelligence is Essential for Machine Learning Models to Truly 'Know When They Do Not Know'](https://mlsanity.com/paper/2505.04950/) (2025)
- [Algorithm- and Data-Dependent Generalization Bounds for Diffusion Models](https://mlsanity.com/paper/2506.03849/) (2025)
- [Generalization Bounds for Markov Algorithms through Entropy Flow Computations](https://mlsanity.com/paper/2502.07584/) (2025)
- [Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes](https://mlsanity.com/paper/2505.19087/) (2025)
- [Generalization at the Edge of Stability](https://mlsanity.com/paper/2604.19740/) (2026)
- [Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds](https://mlsanity.com/paper/2507.06775/) (2025)
- [A neurosymbolic Approach with Epistemic Deep Learning for Hierarchical Image Classification](https://mlsanity.com/paper/2605.16383/) (2026)
- [Generalization in Nonlinear Least Squares via Learned Feature Geometry](https://mlsanity.com/paper/2606.08799/) (2026)
- [A Survey on Data-Dependent Worst-Case Generalization Bounds](https://mlsanity.com/paper/2605.13913/) (2026)

## Abstract (arXiv)

We propose data-dependent uniform generalization bounds by approaching the problem from a PAC-Bayesian perspective. We first apply the PAC-Bayesian framework on "random sets" in a rigorous way, where the training algorithm is assumed to output a data-dependent hypothesis set after observing the training data. This approach allows us to prove data-dependent bounds, which can be applicable in numerous contexts. To highlight the power of our approach, we consider two main applications. First, we propose a PAC-Bayesian formulation of the recently developed fractal-dimension-based generalization bounds. The derived results are shown to be tighter and they unify the existing results around one simple proof technique. Second, we prove uniform bounds over the trajectories of continuous Langevin dynamics and stochastic gradient Langevin dynamics. These results provide novel information about the generalization properties of noisy algorithms.