mlsanityData to 7 Oct 2026

On the role of data in PAC-Bayes bounds

arXiv 2006.10929 ↗First posted 19 Jun 2020cs.LG stat.MLcited by 64

Not on the map. Why?

Abstract (arXiv)

The dominant term in PAC-Bayes bounds is often the Kullback--Leibler divergence between the posterior and prior. For so-called linear PAC-Bayes risk bounds based on the empirical risk of a fixed posterior kernel, it is possible to minimize the expected value of the bound by choosing the prior to be the expected posterior, which we call the oracle prior on the account that it is distribution dependent. In this work, we show that the bound based on the oracle prior can be suboptimal: In some cases, a stronger bound is obtained by using a data-dependent oracle prior, i.e., a conditional expectation of the posterior, given a subset of the training data that is then excluded from the empirical risk term. While using data to learn a prior is a known heuristic, its essential role in optimal bounds is new. In fact, we show that using data can mean the difference between vacuous and nonvacuous bounds. We apply this new principle in the setting of nonconvex learning, simulating data-dependent oracle priors on MNIST and Fashion MNIST with and without held-out data, and demonstrating new nonvacuous bounds in both cases.

Key facts. Cited by 64 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 18; 2022: 17; 2023: 11; 2024: 9; 2025: 7; 2026: 2.

64 papers.

Sort:

By area:

  1. 2021Bayesian Neural Network Priors Revisitedcited by 121
  2. 2023How Does Information Bottleneck Help Deep Learning?cited by 92
  3. 2022PAC-Bayes Compression Bounds So Tight That They Can Explain Generalizationcited by 75
  4. 2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
  5. 2023The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learningcited by 63
  6. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  7. 2022Bayesian Model Selection, the Marginal Likelihood, and Generalizationcited by 56
  8. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  9. 2022Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guaranteescited by 34
  10. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  11. 2021PAC-Bayes Information Bottleneckcited by 28
  12. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
38 more
  1. 2023A Primer on Bayesian Neural Networks: Review and Debatescited by 26
  2. 2024Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Modelscited by 25
  3. 2021How Tight Can PAC-Bayes be in the Small Data Regime?cited by 24
  4. 2022Non-Vacuous Generalisation Bounds for Shallow Neural Networkscited by 22
  5. 2021Learning PAC-Bayes Priors for Probabilistic Neural Networkscited by 21
  6. 2022On PAC-Bayesian reconstruction guarantees for VAEscited by 20
  7. 2021On Margins and Derandomisation in PAC-Bayescited by 19
  8. 2023Fantastic Generalization Measures are Nowhere to be Foundcited by 19
  9. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  10. 2021Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Boundcited by 16
  11. 2021A PAC-Bayes Analysis of Adversarial Robustnesscited by 13
  12. 2021PAC-Bayes Bounds for Meta-learning with Data-Dependent Priorcited by 11
  13. 2022Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practicecited by 11
  14. 2021Progress in Self-Certified Neural Networkscited by 10
  15. 2023Understanding prompt engineering may not require rethinking generalizationcited by 10
  16. 2021Disparity Between Batches as a Signal for Early Stoppingcited by 9
  17. 2022Analyzing Lottery Ticket Hypothesis from PAC-Bayesian Theory Perspectivecited by 9
  18. 2022Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficultycited by 9
  19. 2021Conditionally Gaussian PAC-Bayescited by 7
  20. 2022On Margins and Generalisation for Voting Classifierscited by 7
  21. 2024Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization Bounds with Complexity Measurescited by 7
  22. 2024Statistical Guarantees for Lifelong Reinforcement Learning using PAC-Bayes Theorycited by 7
  23. 2022On the Importance of Gradient Norm in PAC-Bayesian Boundscited by 6
  24. 2023Improving Generalization of Complex Models under Unbounded Loss Using PAC-Bayes Boundscited by 6
  25. 2022Generalization Bounds for Gradient Methods via Discrete and Continuous Priorcited by 5
  26. 2023Comparing Comparators in Generalization Boundscited by 5
  27. 2022PAC-Bayesian Learning of Optimization Algorithmscited by 4
  28. 2024Better-than-KL PAC-Bayes Boundscited by 4
  29. 2025How good is PAC-Bayes at explaining generalisation?cited by 4
  30. 2021PAC Bayesian Performance Guarantees for Deep (Stochastic) Networks in Medical Imagingcited by 3
  31. 2022Controlling Multiple Errors Simultaneously with a PAC-Bayes Boundcited by 3
  32. 2022A General framework for PAC-Bayes Bounds for Meta-Learningcited by 3
  33. 2021Probabilistic fine-tuning of pruning masks and PAC-Bayes self-bounded learningcited by 2
  34. 2024Tighter Generalisation Bounds via Interpolationcited by 2
  35. 2025Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processescited by 2
  36. 2025Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifiercited by 2
  37. 2021Information-Theoretic Bayes Risk Lower Bounds for Realizable Modelscited by 1
  38. 2021PACMAN: PAC-style bounds accounting for the Mismatch between Accuracy and Negative log-losscited by 1

50 most cited of 64 All 64 (JSON)