On the role of data in PAC-Bayes

Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, Daniel RoyAISTATS 2021 · OpenReview

One of the most persistent mysteries in modern artificial intelligence is why deep neural networks generalize so effectively despite having millions of parameters. Theoretical frameworks like PAC-Bayes attempt to explain this by bounding the "generalization gap"—the difference between training error and true test error. However, standard applications of these bounds often fail in deep learning, producing "vacuous" results that predict error rates exceeding 100%.

The Challenge of Vacuous Bounds

The core of a PAC-Bayes bound is the Kullback–Leibler (KL) divergence, which measures the distance between a "prior" distribution (chosen before seeing the data) and a "posterior" distribution (learned from the data). In deep learning, the posterior is highly complex and data-dependent. If the prior is a simple, generic guess, such as a standard Gaussian, the KL divergence explodes. This makes the resulting bound useless for practical insights.

The fundamental question addressed here is: Can we use a portion of our training data to build a better prior? While priors are traditionally independent of the evaluation data, this research explores the optimal trade-off between using data to inform the prior versus using it to estimate the risk.

The α-Prefix Strategy

To apply data-dependent priors to Stochastic Gradient Descent (SGD), the authors introduce the α-prefix strategy. This involves splitting the training process:

  1. Prefix Run: Use an initial fraction (α) of the data to run a prefix of SGD.
  2. Prior Construction: The weights reached at the end of this prefix serve as the mean for a Gaussian prior.
  3. Coupling: To minimize KL divergence, the prefix run and the full "base" run are "coupled" by using the same random initialization and data ordering for the first α fraction of the first epoch.
Visualization of the coupling between weights from the prefix run and the final posterior, showing increasing correlation as training progresses.

This coupling ensures the prior becomes an excellent predictor of the final posterior, significantly reducing the KL term.

The Optimal Data Trade-off

A key insight of this work is the existence of a "sweet spot" for the data fraction α. If α is too small, the prior is uninformed and the KL term remains large. If α is too large, there isn't enough remaining data to provide a reliable estimate of the empirical risk.

The generalization error bound as a function of the data fraction α, illustrating the U-shaped curve and the optimal trade-off point.

Furthermore, the authors observed that most of the variability in SGD's final weights originates at the very beginning of training. By capturing this early trajectory in the prior, the final posterior can be predicted with high accuracy.

Empirical Success and Breakthroughs

The application of these data-dependent priors has led to significant improvements in bound tightness:

  • MNIST Breakthrough: The authors achieved a PAC-Bayes error bound of 11%, a dramatic improvement over the previous best published bound of 46%.
  • Non-Vacuous Fashion MNIST: The method produced the first non-vacuous bounds for this more challenging dataset, which has historically been difficult for PAC-Bayesian analysis.
  • Bound-Driven Learning: Directly optimizing the PAC-Bayes bound as a loss function further improved both the tightness of the bound and the actual classifier accuracy.

Limitations and Future Directions

While this approach marks a significant step toward a meaningful theory of deep learning generalization, challenges remain. The tightest theoretical results currently rely on "ghost samples" (additional held-out data), and choosing the optimal α still requires empirical tuning for new architectures. Scaling these non-vacuous bounds to massive datasets like ImageNet and adapting them for complex optimizers with heavy data augmentation are the next frontiers for this research.

Summary updated

BibTeX
@inproceedings{dziugaite2021role,
  author = {Gintare Karolina Dziugaite and Kyle Hsu and Waseem Gharbieh and Gabriel Arpino and Daniel Roy},
  title = {{On the role of data in PAC-Bayes}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=-TzPnrxfYo},
}
Figure