# PAC-Bayes-Chernoff bounds for unbounded losses

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 74 references that are in the map.
- First posted on arXiv 2 Jan 2024.

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

- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Improving the Adversarial Robustness and Interpretability of Deep Neural Networks by Regularizing their Input Gradients](https://mlsanity.com/paper/1711.09404/) (2017)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015)
- [PAC-Bayesian Theory Meets Bayesian Inference](https://mlsanity.com/paper/1605.08636/) (2016)
- [PAC-Bayes Analysis Beyond the Usual Bounds](https://mlsanity.com/paper/2006.13057/) (2020)
- [Generalization Bounds: Perspectives from Information Theory and PAC-Bayes](https://mlsanity.com/paper/2309.04381/) (2023)
- [Bayesian Model Selection, the Marginal Likelihood, and Generalization](https://mlsanity.com/paper/2202.11678/) (2022)
- [A Strongly Quasiconvex PAC-Bayesian Bound](https://mlsanity.com/paper/1608.05610/) (2016)
- [Scaleable input gradient regularization for adversarial robustness](https://mlsanity.com/paper/1905.11468/) (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 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)
- [Diversity and Generalization in Neural Network Ensembles](https://mlsanity.com/paper/2110.13786/) (2021)
- [Gradient Regularization Improves Accuracy of Discriminative Models](https://mlsanity.com/paper/1712.09936/) (2017)
- [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)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)

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

- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoders](https://mlsanity.com/paper/2512.12905/) (2025)
- [Distributionally Robust PAC-Bayesian Control](https://mlsanity.com/paper/2604.10588/) (2026)
- [Smoothness-Based Derandomization of PAC-Bayes Bounds](https://mlsanity.com/paper/2606.19105/) (2026)
- [How Learning Dynamics Drive Adversarially Robust Generalization?](https://mlsanity.com/paper/2410.07719/) (2024)
- [Beyond NNGP: Large Deviations and Feature Learning in Bayesian Neural Networks](https://mlsanity.com/paper/2602.22925/) (2026)
- [A PAC-Bayesian View of Generalisation for Physics-Informed Machine Learning](https://mlsanity.com/paper/2605.26341/) (2026)
- [PAC-Bayesian Certificates for Quadratic Closed-Loop Control](https://mlsanity.com/paper/2606.28281/) (2026)
- [How Far Can Sharpness and Complexity Jointly Explain Generalization?](https://mlsanity.com/paper/2606.29043/) (2026)

## Abstract (arXiv)

We introduce a new PAC-Bayes oracle bound for unbounded losses that extends Cram'er-Chernoff bounds to the PAC-Bayesian setting. The proof technique relies on controlling the tails of certain random variables involving the Cram'er transform of the loss. Our approach naturally leverages properties of Cram'er-Chernoff bounds, such as exact optimization of the free parameter in many PAC-Bayes bounds. We highlight several applications of the main theorem. Firstly, we show that our bound recovers and generalizes previous results. Additionally, our approach allows working with richer assumptions that result in more informative and potentially tighter bounds. In this direction, we provide a general bound under a new textitmodel-dependent assumption from which we obtain bounds based on parameter norms and log-Sobolev inequalities. Notably, many of these bounds can be minimized to obtain distributions beyond the Gibbs posterior and provide novel theoretical coverage to existing regularization techniques.