# More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 94 references that are in the map.
- First posted on arXiv 21 Jun 2023.

## Builds on (most cited first, 30 of 40)

- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [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)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [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)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [Simpler PAC-Bayesian Bounds for Hostile Data](https://mlsanity.com/paper/1610.07193/) (2016)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [PAC-Bayes unleashed: generalisation bounds with unbounded losses](https://mlsanity.com/paper/2006.07279/) (2020)
- [PAC-Bayes Un-Expected Bernstein Inequality](https://mlsanity.com/paper/1905.13367/) (2019)
- [PAC-Bayes with Backprop](https://mlsanity.com/paper/1908.07380/) (2019)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [A New Family of Generalization Bounds Using Samplewise Evaluated CMI](https://mlsanity.com/paper/2210.06422/) (2022)
- [A Limitation of the PAC-Bayes Framework](https://mlsanity.com/paper/2006.13508/) (2020)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds](https://mlsanity.com/paper/1810.12263/) (2018)
- [How Tight Can PAC-Bayes be in the Small Data Regime?](https://mlsanity.com/paper/2106.03542/) (2021)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [PAC-Bayesian Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1910.04464/) (2019)
- [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022)
- [Integral Probability Metrics PAC-Bayes Bounds](https://mlsanity.com/paper/2207.00614/) (2022)

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

- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [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)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [Empirical PAC-Bayes Bounds for Markov Chains](https://mlsanity.com/paper/2509.20985/) (2025)
- [PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoders](https://mlsanity.com/paper/2512.12905/) (2025)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Refined PAC-Bayes Bounds for Offline Bandits](https://mlsanity.com/paper/2502.11953/) (2025)
- [The Alignment Bottleneck](https://mlsanity.com/paper/2509.15932/) (2025)
- [Generalization Guarantees on Data-Driven Tuning of Gradient Descent with Langevin Updates](https://mlsanity.com/paper/2604.13130/) (2026)
- [Non-vacuous Generalization Bounds for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2607.14506/) (2026)
- [A note on generalization bounds for losses with finite moments](https://mlsanity.com/paper/2403.16681/) (2024)
- [Position: Many generalization measures for deep learning are fragile](https://mlsanity.com/paper/2510.18934/) (2025)
- [A PAC-Bayesian View of Generalisation for Physics-Informed Machine Learning](https://mlsanity.com/paper/2605.26341/) (2026)
- [How Far Can Sharpness and Complexity Jointly Explain Generalization?](https://mlsanity.com/paper/2606.29043/) (2026)
- [Certification Frontiers for Gaussian LoRA: Independent Priors, Posterior Risk, and Prediction-Preserving Balancing](https://mlsanity.com/paper/2609.32271/) (2026)

## Abstract (arXiv)

In this paper, we present new high-probability PAC-Bayes bounds for different types of losses. Firstly, for losses with a bounded range, we recover a strengthened version of Catoni's bound that holds uniformly for all parameter values. This leads to new fast-rate and mixed-rate bounds that are interpretable and tighter than previous bounds in the literature. In particular, the fast-rate bound is equivalent to the Seeger--Langford bound. Secondly, for losses with more general tail behaviors, we introduce two new parameter-free bounds: a PAC-Bayes Chernoff analogue when the loss' cumulative generating function is bounded, and a bound when the loss' second moment is bounded. These two bounds are obtained using a new technique based on a discretization of the space of possible events for the ``in probability'' parameter optimization problem. This technique is both simpler and more general than previous approaches optimizing over a grid on the parameters' space. Finally, using a simple technique that is applicable to any existing bound, we extend all previous results to anytime-valid bounds.