mlsanityData to 7 Oct 2026

Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty

arXiv 2210.11289 ↗First posted 20 Oct 2022cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

We introduce a modified version of the excess risk, which can be used to obtain tighter, fast-rate PAC-Bayesian generalisation bounds. This modified excess risk leverages information about the relative hardness of data examples to reduce the variance of its empirical counterpart, tightening the bound. We combine this with a new bound for [-1, 1]-valued (and potentially non-independent) signed losses, which is more favourable when they empirically have low variance around 0. The primary new technical tool is a novel result for sequences of interdependent random vectors which may be of independent interest. We empirically evaluate these new bounds on a number of real-world datasets.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 24 of its 41 references that are in the map. First posted on arXiv 20 Oct 2022.

Builds on

24 of 41 references.

References · 24

  1. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  2. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  3. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  4. 2019A Primer on PAC-Bayesian Learningcited by 130
  5. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 125
  6. 2020Tighter risk certificates for neural networkscited by 112
  7. 2017Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priorscited by 81
  8. 2020On the role of data in PAC-Bayes boundscited by 64
  9. 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
  10. 2019PAC-Bayes Un-Expected Bernstein Inequalitycited by 36
  11. 2020Second Order PAC-Bayesian Bounds for the Weighted Majority Votecited by 34
  12. 2020Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networkscited by 29
12 more
  1. 2021How Tight Can PAC-Bayes be in the Small Data Regime?cited by 24
  2. 2022Non-Vacuous Generalisation Bounds for Shallow Neural Networkscited by 22
  3. 2018PAC-Bayes bounds for stable algorithms with instance-dependent priorscited by 21
  4. 2021Learning PAC-Bayes Priors for Probabilistic Neural Networkscited by 21
  5. 2021Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Boundcited by 16
  6. 2022Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variablescited by 11
  7. 2022Change of measure through the Legendre transformcited by 10
  8. 2022A Note on the Chernoff Bound for Random Variables in the Unit Intervalcited by 7
  9. 2022On Margins and Generalisation for Voting Classifierscited by 7
  10. 2022Controlling Multiple Errors Simultaneously with a PAC-Bayes Boundcited by 3
  11. 2020Multicritera Cuts and Size-Constrained k-cuts in Hypergraphscited by 2
  12. 2022A Note on the Efficient Evaluation of PAC-Bayes Boundscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 2; 2025: 3; 2026: 1.

9 papers.

  1. 2023MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splittingcited by 33
  2. 2023Learning via Wasserstein-Based High Probability Generalisation Boundscited by 11
  3. 2024Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Losscited by 4
  4. 2024Gentle Local Robustness implies Generalizationcited by 4
  5. 2025Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained modelscited by 2
  6. 2025Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifiercited by 2
  7. 2025Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?cited by 1
  8. 2023The surrogate Gibbs-posterior of a corrected stochastic MALA: Towards uncertainty quantification for neural networkscited by 0
  9. 2026PAC-DP: PAC-Bayesian Diffusion Policy Learningcited by 0