mlsanityData to 7 Oct 2026

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

arXiv 2404.17442 ↗First posted 26 Apr 2024stat.ML cs.LGcited by 9

Not on the map. Why?

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.

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

Builds on

34 of 69 references.

References · 34

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  3. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  4. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  5. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  6. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  7. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  8. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  9. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  10. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  11. 2020The Heavy-Tail Phenomenon in SGDcited by 122
  12. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
22 more
  1. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  2. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  3. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  4. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
  5. 2021Intrinsic Dimension, Persistent Homology and Generalization in Neural Networkscited by 70
  6. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
  7. 2020Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networkscited by 62
  8. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  9. 2015Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithmcited by 50
  10. 2017A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descentcited by 29
  11. 2021Generalization Bounds using Lower Tail Exponents in Stochastic Optimizerscited by 27
  12. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  13. 2023A unified recipe for deriving (time-uniform) PAC-Bayes boundscited by 25
  14. 2019Hypothesis Set Stability and Generalizationcited by 23
  15. 2021Fractal Structure and Generalization Properties of Stochastic Optimization Algorithmscited by 23
  16. 2021A General Framework for the Practical Disintegration of PAC-Bayesian Boundscited by 21
  17. 2020On the Rademacher Complexity of Linear Hypothesis Setscited by 17
  18. 2021Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Boundcited by 16
  19. 2023Time-Independent Information-Theoretic Generalization Bounds for SGLDcited by 12
  20. 2022Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimizationcited by 7
  21. 2023Generalization Guarantees via Algorithm-dependent Rademacher Complexitycited by 4
  22. 2023From Mutual Information to Expected Dynamics: New Generalization Bounds for Heavy-Tailed SGDcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 4.

9 papers.

  1. 2025Epistemic Artificial Intelligence is Essential for Machine Learning Models to Truly 'Know When They Do Not Know'cited by 8
  2. 2025Algorithm- and Data-Dependent Generalization Bounds for Diffusion Modelscited by 4
  3. 2025Generalization Bounds for Markov Algorithms through Entropy Flow Computationscited by 2
  4. 2025Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processescited by 2
  5. 2025Stability, Complexity and Data-Dependent Worst-Case Generalization Boundscited by 1
  6. 2026A neurosymbolic Approach with Epistemic Deep Learning for Hierarchical Image Classificationcited by 1
  7. 2026Generalization in Nonlinear Least Squares via Learned Feature Geometrycited by 1
  8. 2026Generalization at the Edge of Stabilitycited by 0
  9. 2026A Survey on Data-Dependent Worst-Case Generalization Boundscited by 0