mlsanityData to 14 Oct 2026

PAC-Bayes Un-Expected Bernstein Inequality

arXiv 1905.13367 ↗First posted 31 May 2019cs.LG stat.MLcited by 36

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 10; 2023: 9; 2024: 6; 2025: 5; 2026: 2.

36 papers.

Sort:

By area:

  1. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  2. 2021Tight Concentrations and Confidence Sequences from the Regret of Universal Portfoliocited by 43
  3. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  4. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
  5. 2022PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingalescited by 24
  6. 2022Online PAC-Bayes Learningcited by 22
  7. 2022On PAC-Bayesian reconstruction guarantees for VAEscited by 20
  8. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  9. 2021Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Boundcited by 16
  10. 2023Online-to-PAC Conversions: Generalization Bounds via Regret Analysiscited by 14
  11. 2022Instance-Dependent Generalization Bounds via Optimal Transportcited by 13
  12. 2023Tighter PAC-Bayes Bounds Through Coin-Bettingcited by 13
24 more
  1. 2024A PAC-Bayesian Link Between Generalisation and Flat Minimacited by 13
  2. 2023Learning via Wasserstein-Based High Probability Generalisation Boundscited by 12
  3. 2022Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variablescited by 11
  4. 2022On the Generalization for Transfer Learning: An Information-Theoretic Analysiscited by 11
  5. 2022Minimax risk classifiers with 0-1 losscited by 9
  6. 2022Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficultycited by 9
  7. 2023A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regressioncited by 8
  8. 2022Fast Rate Generalization Error Bounds: Variations on a Themecited by 6
  9. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 6
  10. 2023Fast Rate Information-theoretic Bounds on Generalization Errorscited by 5
  11. 2024Better-than-KL PAC-Bayes Boundscited by 4
  12. 2024Probabilistic Generating Circuits -- Demystifiedcited by 4
  13. 2024Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Losscited by 4
  14. 2025How good is PAC-Bayes at explaining generalisation?cited by 4
  15. 2023Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisationcited by 3
  16. 2025Secrets of GFlowNets' Learning Behavior: A Theoretical Studycited by 3
  17. 2025Empirical PAC-Bayes Bounds for Markov Chainscited by 3
  18. 2023Federated Learning with Nonvacuous Generalisation Boundscited by 2
  19. 2024Sharp Matrix Empirical Bernstein Inequalitiescited by 2
  20. 2024Learning via Surrogate PAC-Bayescited by 1
  21. 2025Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?cited by 1
  22. 2025Deep Actor-Critics with Tight Risk Certificatescited by 0
  23. 2026Misclassification Rate and Privacy-Utility Trade-offs in Graph Convolutional Networks via Subsampling Stabilitycited by 0
  24. 2026On the disintegration of the stochastic majority vote: From PAC-Bayesian bounds to a self-bounding algorithmcited by 0