PAC-Bayes bounds

Instead of betting on a single hypothesis, imagine carrying a whole probability distribution over hypotheses and drawing one at random each time you predict. PAC-Bayes bounds the average true risk of such a randomized predictor by its average empirical risk plus a penalty — and that penalty is the information you spent moving from a prior distribution, chosen before seeing data, to a posterior, chosen after. Stay close to your prior and you pay little; stray far to fit the data and you pay for it in generalization.

For a prior and any data-dependent posterior over hypotheses, with probability at least one minus delta the gap between the posterior's expected true and empirical risks is bounded in terms of the Kullback–Leibler divergence from posterior to prior, plus a logarithmic confidence term, all divided by the sample size and typically under a square root. The bound holds simultaneously for every posterior, so the learner may optimize the posterior to minimize the right-hand side. Because the divergence replaces any explicit capacity measure, the bound adapts to whatever posterior the algorithm actually produces.

PAC-Bayes gives some of the only non-vacuous generalization bounds for large neural networks, by exploiting flatness: a posterior that can be perturbed without raising training error has small divergence to a broad prior. It also unifies with Bayesian inference and information-theoretic generalization and underlies practical regularizers and self-bounded learning. The catch is that the bounds govern the randomized Gibbs predictor; derandomizing to a single deterministic network can lose tightness.