A Limitation of the PAC-Bayes Framework
Lists
Only you see this
Abstract
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/\delta)/\epsilon)$ 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.
BibTeX
@inproceedings{livni2020limitation,
author = {Roi Livni and Shay Moran},
title = {{A Limitation of the PAC-Bayes Framework}},
booktitle = {Advances in Neural Information Processing Systems},
year = {2020},
url = {https://openreview.net/forum?id=UijtDWZYywX},
}| PAC-Bayes bounds for stable algorithms with instance-dependent priors | arXiv · 2018 |
| PAC-Bayes-Chernoff bounds for unbounded losses | arXiv · 2024 |
| How good is PAC-Bayes at explaining generalisation? | arXiv · 2025 |
| A DPI-PAC-Bayesian Framework for Generalization Bounds | arXiv · 2025 |
| User-friendly introduction to PAC-Bayes bounds | Found. Trends Mach. Learn · 2024 |
| PAC-Bayes Analysis Beyond the Usual Bounds | arXiv · 2020 |