# Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty

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

## Key facts

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

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

- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors](https://mlsanity.com/paper/1712.09376/) (2017)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks](https://mlsanity.com/paper/1905.10259/) (2019)
- [PAC-Bayes Un-Expected Bernstein Inequality](https://mlsanity.com/paper/1905.13367/) (2019)
- [Second Order PAC-Bayesian Bounds for the Weighted Majority Vote](https://mlsanity.com/paper/2007.13532/) (2020)
- [Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks](https://mlsanity.com/paper/2006.12228/) (2020)
- [How Tight Can PAC-Bayes be in the Small Data Regime?](https://mlsanity.com/paper/2106.03542/) (2021)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [PAC-Bayes bounds for stable algorithms with instance-dependent priors](https://mlsanity.com/paper/1806.06827/) (2018)
- [Learning PAC-Bayes Priors for Probabilistic Neural Networks](https://mlsanity.com/paper/2109.10304/) (2021)
- [Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound](https://mlsanity.com/paper/2106.12535/) (2021)
- [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022)
- [Change of measure through the Legendre transform](https://mlsanity.com/paper/2202.05568/) (2022)
- [A Note on the Chernoff Bound for Random Variables in the Unit Interval](https://mlsanity.com/paper/2205.07880/) (2022)
- [On Margins and Generalisation for Voting Classifiers](https://mlsanity.com/paper/2206.04607/) (2022)
- [Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound](https://mlsanity.com/paper/2202.05560/) (2022)
- [Multicritera Cuts and Size-Constrained k-cuts in Hypergraphs](https://mlsanity.com/paper/2006.11589/) (2020)
- [A Note on the Efficient Evaluation of PAC-Bayes Bounds](https://mlsanity.com/paper/2209.05188/) (2022)

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

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss](https://mlsanity.com/paper/2405.14681/) (2024)
- [Gentle Local Robustness implies Generalization](https://mlsanity.com/paper/2412.06381/) (2024)
- [Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models](https://mlsanity.com/paper/2503.07325/) (2025)
- [Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier](https://mlsanity.com/paper/2509.25979/) (2025)
- [Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?](https://mlsanity.com/paper/2509.26149/) (2025)
- [The surrogate Gibbs-posterior of a corrected stochastic MALA: Towards uncertainty quantification for neural networks](https://mlsanity.com/paper/2310.09335/) (2023)
- [PAC-DP: PAC-Bayesian Diffusion Policy Learning](https://mlsanity.com/paper/2607.24296/) (2026)

## 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.