# A Limitation of the PAC-Bayes Framework

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2020.

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [Integral Probability Metrics PAC-Bayes Bounds](https://mlsanity.com/paper/2207.00614/) (2022)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [Information Complexity and Generalization Bounds](https://mlsanity.com/paper/2105.01747/) (2021)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [Strong Memory Lower Bounds for Learning Natural Models](https://mlsanity.com/paper/2206.04743/) (2022)
- [Finite Littlestone Dimension Implies Finite Information Complexity](https://mlsanity.com/paper/2206.13257/) (2022)
- [Improving Generalization of Complex Models under Unbounded Loss Using PAC-Bayes Bounds](https://mlsanity.com/paper/2305.19243/) (2023)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Trade-offs in Data Memorization via Strong Data Processing Inequalities](https://mlsanity.com/paper/2506.01855/) (2025)
- [A Unified Characterization of Private Learnability via Graph Theory](https://mlsanity.com/paper/2304.03996/) (2023)
- [The unstable formula theorem revisited via algorithms](https://mlsanity.com/paper/2212.05050/) (2022)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)
- [Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier](https://mlsanity.com/paper/2509.25979/) (2025)
- [Generalization within in silico screening](https://mlsanity.com/paper/2307.09379/) (2023)
- [Why Heavy-Tailed Weight Spectra Predict Model Quality](https://mlsanity.com/paper/2610.13123/) (2026)

## 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.