# How Tight Can PAC-Bayes be in the Small Data Regime?

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 7 Jun 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Conditional Neural Processes](https://mlsanity.com/paper/1807.01613/) (2018)
- [Neural Processes](https://mlsanity.com/paper/1807.01622/) (2018)
- [Attentive Neural Processes](https://mlsanity.com/paper/1901.05761/) (2019)
- [Convolutional Conditional Neural Processes](https://mlsanity.com/paper/1910.13556/) (2019)
- [Inference Suboptimality in Variational Autoencoders](https://mlsanity.com/paper/1801.03558/) (2018)
- [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)
- [PAC-Bayesian Theory Meets Bayesian Inference](https://mlsanity.com/paper/1605.08636/) (2016)
- [PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees](https://mlsanity.com/paper/2002.05551/) (2020)
- [Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory](https://mlsanity.com/paper/1711.01244/) (2017)
- [Meta-Learning Stationary Stochastic Process Prediction with Convolutional Neural Processes](https://mlsanity.com/paper/2007.01332/) (2020)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [PAC-Bayes Analysis Beyond the Usual Bounds](https://mlsanity.com/paper/2006.13057/) (2020)
- [A Strongly Quasiconvex PAC-Bayesian Bound](https://mlsanity.com/paper/1608.05610/) (2016)
- [Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm](https://mlsanity.com/paper/1503.08329/) (2015)
- [Simpler PAC-Bayesian Bounds for Hostile Data](https://mlsanity.com/paper/1610.07193/) (2016)
- [A PAC-Bayesian Tutorial with A Dropout Bound](https://mlsanity.com/paper/1307.2118/) (2013)
- [PAC-Bayes with Backprop](https://mlsanity.com/paper/1908.07380/) (2019)
- [Second Order PAC-Bayesian Bounds for the Weighted Majority Vote](https://mlsanity.com/paper/2007.13532/) (2020)
- [The Gaussian Neural Process](https://mlsanity.com/paper/2101.03606/) (2021)
- [PAC-Bayes Bounds for Meta-learning with Data-Dependent Prior](https://mlsanity.com/paper/2102.03748/) (2021)

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022)
- [Progress in Self-Certified Neural Networks](https://mlsanity.com/paper/2111.07737/) (2021)
- [PAC-tuning:Fine-tuning Pretrained Language Models with PAC-driven Perturbed Gradient Descent](https://mlsanity.com/paper/2310.17588/) (2023)
- [Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty](https://mlsanity.com/paper/2210.11289/) (2022)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [On Margins and Generalisation for Voting Classifiers](https://mlsanity.com/paper/2206.04607/) (2022)
- [PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison](https://mlsanity.com/paper/2211.16110/) (2022)
- [On the Importance of Gradient Norm in PAC-Bayesian Bounds](https://mlsanity.com/paper/2210.06143/) (2022)
- [Comparing Comparators in Generalization Bounds](https://mlsanity.com/paper/2310.10534/) (2023)
- [Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss](https://mlsanity.com/paper/2405.14681/) (2024)
- [PAC-Bayes Analysis for Recalibration in Classification](https://mlsanity.com/paper/2406.06227/) (2024)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [Model Merging is Secretly Certifiable: Non-Vacuous Generalisation Bounds for Low-Shot Learning](https://mlsanity.com/paper/2505.15798/) (2025)
- [Bound to Disagree: Generalization Bounds via Certifiable Surrogates](https://mlsanity.com/paper/2602.23128/) (2026)
- [Estimating optimal PAC-Bayes bounds with Hamiltonian Monte Carlo](https://mlsanity.com/paper/2310.20053/) (2023)
- [Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds](https://mlsanity.com/paper/2411.06276/) (2024)
- [A DPI-PAC-Bayesian Framework for Generalization Bounds](https://mlsanity.com/paper/2507.14795/) (2025)
- [Feature Noise Boosts DNN Generalization under Label Noise](https://mlsanity.com/paper/2308.01609/) (2023)
- [Something for (almost) nothing: Improving deep ensemble calibration using unlabeled data](https://mlsanity.com/paper/2310.02885/) (2023)
- [Deep Actor-Critics with Tight Risk Certificates](https://mlsanity.com/paper/2505.19682/) (2025)
- [Block-Sample MAC-Bayes Generalization Bounds](https://mlsanity.com/paper/2602.12605/) (2026)
- [Certification of Machine Learning Models via Directional Sharpness](https://mlsanity.com/paper/2606.25004/) (2026)

## Abstract (arXiv)

In this paper, we investigate the question: Given a small number of datapoints, for example N = 30, how tight can PAC-Bayes and test set bounds be made? For such small datasets, test set bounds adversely affect generalisation performance by withholding data from the training procedure. In this setting, PAC-Bayes bounds are especially attractive, due to their ability to use all the data to simultaneously learn a posterior and bound its generalisation risk. We focus on the case of i.i.d. data with a bounded loss and consider the generic PAC-Bayes theorem of Germain et al. While their theorem is known to recover many existing PAC-Bayes bounds, it is unclear what the tightest bound derivable from their framework is. For a fixed learning algorithm and dataset, we show that the tightest possible bound coincides with a bound considered by Catoni; and, in the more natural case of distributions over datasets, we establish a lower bound on the best bound achievable in expectation. Interestingly, this lower bound recovers the Chernoff test set bound if the posterior is equal to the prior. Moreover, to illustrate how tight these bounds can be, we study synthetic one-dimensional classification tasks in which it is feasible to meta-learn both the prior and the form of the bound to numerically optimise for the tightest bounds possible. We find that in this simple, controlled scenario, PAC-Bayes bounds are competitive with comparable, commonly used Chernoff test set bounds. However, the sharpest test set bounds still lead to better guarantees on the generalisation error than the PAC-Bayes bounds we consider.