mlsanityData to 14 Oct 2026

Comparing Comparators in Generalization Bounds

arXiv 2310.10534 ↗First posted 16 Oct 2023cs.LG cs.IT math.ITcited by 5

Not on the map. Why?

Abstract (arXiv)

We derive generic information-theoretic and PAC-Bayesian generalization bounds involving an arbitrary convex comparator function, which measures the discrepancy between the training and population loss. The bounds hold under the assumption that the cumulant-generating function (CGF) of the comparator is upper-bounded by the corresponding CGF within a family of bounding distributions. We show that the tightest possible bound is obtained with the comparator being the convex conjugate of the CGF of the bounding distribution, also known as the Cram'er function. This conclusion applies more broadly to generalization bounds with a similar structure. This confirms the near-optimality of known bounds for bounded and sub-Gaussian losses and leads to novel bounds under other bounding distributions.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 35 of its 79 references that are in the map. First posted on arXiv 16 Oct 2023.

Builds on

35 of 79 references.

References · 35

  1. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  2. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 314
  3. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  4. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  5. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 147
  6. 2019A Primer on PAC-Bayesian Learningcited by 132
  7. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 126
  8. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 119
  9. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  10. 2020Tighter risk certificates for neural networkscited by 112
  11. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  12. 2016PAC-Bayesian Theory Meets Bayesian Inferencecited by 88
23 more
  1. 2022PAC-Bayes Compression Bounds So Tight That They Can Explain Generalizationcited by 76
  2. 2020On the role of data in PAC-Bayes boundscited by 64
  3. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
  4. 2023Generalization Bounds: Perspectives from Information Theory and PAC-Bayescited by 61
  5. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  6. 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 46
  7. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  8. 2020PAC-Bayes unleashed: generalisation bounds with unbounded lossescited by 43
  9. 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
  10. 2020Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networkscited by 29
  11. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  12. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
  13. 2021How Tight Can PAC-Bayes be in the Small Data Regime?cited by 24
  14. 2022PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingalescited by 24
  15. 2022Non-Vacuous Generalisation Bounds for Shallow Neural Networkscited by 22
  16. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 22
  17. 2021On Margins and Derandomisation in PAC-Bayescited by 19
  18. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  19. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
  20. 2021Information Complexity and Generalization Boundscited by 14
  21. 2023Online-to-PAC Conversions: Generalization Bounds via Regret Analysiscited by 14
  22. 2020PAC-Bayesian Bound for the Conditional Value at Riskcited by 13
  23. 2023Fast Rate Information-theoretic Bounds on Generalization Errorscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 1.

5 papers.

  1. 2024PAC-Bayes-Chernoff bounds for unbounded lossescited by 9
  2. 2024Sample Compression Unleashed: New Generalization Bounds for Real Valued Lossescited by 4
  3. 2025Generalization in Federated Learning: A Conditional Mutual Information Frameworkcited by 2
  4. 2025Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?cited by 1
  5. 2026Block-Sample MAC-Bayes Generalization Boundscited by 0