# PAC-Bayes Un-Expected Bernstein Inequality

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2019.

## Built on by (most cited first, 30 of 36)

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [A New Family of Generalization Bounds Using Samplewise Evaluated CMI](https://mlsanity.com/paper/2210.06422/) (2022)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Online PAC-Bayes Learning](https://mlsanity.com/paper/2206.00024/) (2022)
- [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound](https://mlsanity.com/paper/2106.12535/) (2021)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Instance-Dependent Generalization Bounds via Optimal Transport](https://mlsanity.com/paper/2211.01258/) (2022)
- [Tighter PAC-Bayes Bounds Through Coin-Betting](https://mlsanity.com/paper/2302.05829/) (2023)
- [A PAC-Bayesian Link Between Generalisation and Flat Minima](https://mlsanity.com/paper/2402.08508/) (2024)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022)
- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (2022)
- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty](https://mlsanity.com/paper/2210.11289/) (2022)
- [A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regression](https://mlsanity.com/paper/2310.00987/) (2023)
- [Fast Rate Generalization Error Bounds: Variations on a Theme](https://mlsanity.com/paper/2205.03131/) (2022)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Fast Rate Information-theoretic Bounds on Generalization Errors](https://mlsanity.com/paper/2303.14658/) (2023)
- [Better-than-KL PAC-Bayes Bounds](https://mlsanity.com/paper/2402.09201/) (2024)
- [Probabilistic Generating Circuits -- Demystified](https://mlsanity.com/paper/2404.02912/) (2024)
- [Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss](https://mlsanity.com/paper/2405.14681/) (2024)
- [How good is PAC-Bayes at explaining generalisation?](https://mlsanity.com/paper/2503.08231/) (2025)
- [Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation](https://mlsanity.com/paper/2304.07048/) (2023)
- [Secrets of GFlowNets' Learning Behavior: A Theoretical Study](https://mlsanity.com/paper/2505.02035/) (2025)
- [Empirical PAC-Bayes Bounds for Markov Chains](https://mlsanity.com/paper/2509.20985/) (2025)
- [Federated Learning with Nonvacuous Generalisation Bounds](https://mlsanity.com/paper/2310.11203/) (2023)

## Abstract (arXiv)

We present a new PAC-Bayesian generalization bound. Standard bounds contain a √Ln · KL/n complexity term which dominates unless Ln, the empirical error of the learning algorithm's randomized predictions, vanishes. We manage to replace Ln by a term which vanishes in many more situations, essentially whenever the employed learning algorithm is sufficiently stable on the dataset at hand. Our new bound consistently beats state-of-the-art bounds both on a toy example and on UCI datasets (with large enough n). Theoretically, unlike existing bounds, our new bound can be expected to converge to 0 faster whenever a Bernstein/Tsybakov condition holds, thus connecting PAC-Bayesian generalization and em excess risk/ bounds---for the latter it has long been known that faster convergence can be obtained under Bernstein conditions. Our main technical tool is a new concentration inequality which is like Bernstein's but with X2 taken outside its expectation.