mlsanityData to 7 Oct 2026

A Limitation of the PAC-Bayes Framework

arXiv 2006.13508 ↗First posted 24 Jun 2020cs.LG stat.MLcited by 24

Not on the map. Why?

Abstract (arXiv)

PAC-Bayes is a useful framework for deriving generalization bounds which was introduced by McAllester ('98). This framework has the flexibility of deriving distribution- and algorithm-dependent bounds, which are often tighter than VC-related uniform convergence bounds. In this manuscript we present a limitation for the PAC-Bayes framework. We demonstrate an easy learning task that is not amenable to a PAC-Bayes analysis. Specifically, we consider the task of linear classification in 1D; it is well-known that this task is learnable using just O(log(1/δ)/ε) examples. On the other hand, we show that this fact can not be proved using a PAC-Bayes analysis: for any algorithm that learns 1-dimensional linear classifiers there exists a (realizable) distribution for which the PAC-Bayes bound is arbitrarily large.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 6; 2023: 10; 2024: 1; 2025: 3.

24 papers.

Sort:

  1. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  2. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  3. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  4. 2023A unified recipe for deriving (time-uniform) PAC-Bayes boundscited by 25
  5. 2022Integral Probability Metrics PAC-Bayes Boundscited by 19
  6. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  7. 2023Statistical Indistinguishability of Learning Algorithmscited by 17
  8. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  9. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
  10. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  11. 2021Information Complexity and Generalization Boundscited by 14
  12. 2023Online-to-PAC Conversions: Generalization Bounds via Regret Analysiscited by 14
12 more
  1. 2023The Bayesian Stability Zoocited by 13
  2. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  3. 2022Strong Memory Lower Bounds for Learning Natural Modelscited by 10
  4. 2022Finite Littlestone Dimension Implies Finite Information Complexitycited by 7
  5. 2023Improving Generalization of Complex Models under Unbounded Loss Using PAC-Bayes Boundscited by 6
  6. 2023A Unified Characterization of Private Learnability via Graph Theorycited by 5
  7. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 5
  8. 2025Trade-offs in Data Memorization via Strong Data Processing Inequalitiescited by 5
  9. 2022The unstable formula theorem revisited via algorithmscited by 4
  10. 2025Private List Learnability vs. Online List Learnabilitycited by 2
  11. 2025Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifiercited by 2
  12. 2023Generalization within in silico screeningcited by 0