A Limitation of the PAC-Bayes Framework

Roi Livni, Shay Moran

Introduction

The PAC-Bayes framework, introduced by McAllester in 1998, is a cornerstone of machine learning theory. It is celebrated for its ability to provide tight, distribution- and algorithm-dependent generalization bounds. Unlike traditional VC-dimension bounds, which are often "one-size-fits-all," PAC-Bayes allows for flexibility by measuring the Kullback-Leibler (KL) divergence between a prior belief and a posterior distribution over classifiers.

However, a fundamental question has persisted in learning theory: Is every task that is "learnable" in the standard sense also explainable via PAC-Bayes? This paper proves a surprising negative answer, demonstrating a fundamental "blind spot" in the framework using one of the simplest learning tasks imaginable: 1-dimensional linear classification (thresholding).

The Core Problem

1D thresholding (e.g., determining if $x > k$) is the "Hello World" of machine learning theory. It is well-established that this task is easily learnable with a sample complexity of $O(\log(1/\delta)/\epsilon)$, entirely independent of the domain size.

The authors set out to prove that PAC-Bayes cannot provide a non-vacuous (useful) bound for this simple task. They demonstrate that the resulting bounds can be forced to become arbitrarily large regardless of the algorithm or prior used, exposing a scenario where the theoretical framework fails to capture the practical reality of learnability.

Theoretical Framework and Methodology

As a purely theoretical work, the paper employs sophisticated mathematical tools to establish a lower bound on PAC-Bayes quantities. The methodology relies on several key technical steps:

  • Ramsey Theory: The authors use Ramsey Theory to identify a large "homogeneous" subset of the domain. Within this subset, any arbitrary learning algorithm is forced to behave in a highly regular and predictable manner.
  • Sensitivity Lemma: They prove that if an algorithm successfully learns thresholds, it must be "sensitive" to small changes in the input sample.
  • Information-Theoretic Lower Bounds: By combining homogeneity and sensitivity, the authors show that this required sensitivity forces the KL divergence between the algorithm's output and any fixed prior to explode as the domain size increases.
  • Algorithm-Dependent Hard Distributions: Diverging from standard "No-Free-Lunch" theorems that use a single hard distribution for all algorithms, the authors construct a specific hard distribution for any chosen algorithm, rendering its PAC-Bayes bound vacuous.

Key Results and Insights

The paper's findings highlight a stark contrast between actual learnability and PAC-Bayes explainability:

  • Theorem 2 (Main Result): For any learning algorithm $A$ and any sample size $m$, there exists a realizable distribution $D$ such that for any prior $P$, the PAC-Bayes bound is essentially useless. Specifically, either the KL divergence is prohibitively large, or the classifier's error is high (greater than $1/4$).
  • Corollary 1: The PAC-learnability of linear classifiers cannot be explained by the PAC-Bayes framework.
  • Domain Dependence: The paper reveals that for thresholds, any PAC-Bayes bound must scale with the size of the domain—specifically, an iterated logarithm of the domain size, $\log^{(m)}(n)$. While this growth is slow, it tends to infinity as the domain grows, sharply contrasting with the true, constant sample complexity of the problem.
  • Limits of Flexibility: PAC-Bayes is often praised because the prior can be distribution-dependent. The authors show that even this ultimate flexibility is insufficient to salvage the framework for 1D thresholds.

Limitations and Future Directions

While the paper establishes a strict theoretical limitation, it also opens several avenues for future inquiry:

  • Mild Dependence: The dependence on domain size is "mild" (iterated logarithms). This leaves open the practical question of whether PAC-Bayes remains "good enough" for finite-sized problems, even if it theoretically fails in the limit.
  • Sample Complexity Gap: The findings do not rule out the possibility that PAC-Bayes could succeed if the sample complexity were allowed to grow slightly with the domain size (e.g., $O(\log^* n)$).
  • Privacy and Generalization: The proof techniques draw heavy inspiration from Differential Privacy. The authors suggest a deep link between the limitations of PAC-Bayes and the "stability" (or lack thereof) required by certain learning tasks, indicating that the mathematical failure modes of both fields are related.
  • Broader Classes: While this paper focuses on 1D thresholds, a natural next step is to identify what other, more complex hypothesis classes share this PAC-Bayes blind spot.

Summary updated

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 which 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},
}
Figure