PAC-Bayes Bounds

VC-style bounds measure a hypothesis class's worst-case flexibility and apply that same penalty to every hypothesis inside it, regardless of how the learning algorithm behaved — wasteful, since most algorithms don't explore the class impartially, they favor hypotheses close to some sensible starting point. PAC-Bayes bounds exploit that: instead of bounding a single hypothesis or an entire class uniformly, they bound the expected error of a distribution over hypotheses — a "posterior belief" — penalized by how far that belief moved from a "prior belief" chosen before seeing any data. A process that ends up close to a sensible prior gets a tight bound; one that drifted wildly gets a loose one, proportional to how much flexibility the algorithm actually used, not the class's worst case.

The analogy: how much did the evidence change your mind

Imagine two analysts forming a view on a stock. Analyst A starts with a well-reasoned prior view and, after reading the earnings report, adjusts it only slightly — their final view stays close to where a sensible, evidence-agnostic starting point would put them. Analyst B starts with no real prior view at all and ends up somewhere wildly specific after the same report — a view that looks suspiciously tailored to that one report's exact numbers. Analyst A's small adjustment is more trustworthy precisely because it required less "explaining away" of the report to reach; Analyst B's large, specific swing is the kind of move that overfits to one report's idiosyncrasies. PAC-Bayes literally measures this: the "distance moved" from prior to posterior belief, and penalizes large, specific moves more than small, well-anchored ones.

The formal bound

Let $P$ be a prior distribution over hypotheses chosen before seeing data, and $Q$ a posterior distribution the learning algorithm outputs after seeing $n$ examples. With probability at least $1-\delta$:

$$\mathbb{E}_{h \sim Q}[R(h)] \le \mathbb{E}_{h \sim Q}[\hat{R}(h)] + \sqrt{\frac{\text{KL}(Q \| P) + \ln(n/\delta)}{2n}}$$

In words: the average true error of hypotheses drawn from your posterior belief $Q$ is bounded by their average training error, plus a penalty that grows with $\text{KL}(Q\|P)$ — the Kullback-Leibler divergence, a measure of how far the posterior $Q$ has moved from the prior $P$ (in bits, roughly "how surprised would you be seeing $Q$-typical hypotheses if you expected $P$-typical ones"). A posterior that stays close to a well-chosen prior pays a small penalty regardless of how large or flexible the underlying hypothesis class is; a posterior that wanders far pays proportionally more.

Worked example 1: a tight bound from a sensible prior

A prior $P$ is a broad Gaussian centered at zero over a neural network's weights (a standard random initialization). After training on $n=10{,}000$ examples, the posterior $Q$ ends up as a narrower Gaussian centered near that same origin — $\text{KL}(Q\|P) \approx 200$, a modest divergence for a network that mostly used regularization to stay anchored. The penalty term is $\sqrt{\frac{200 + \ln(200{,}000)}{20{,}000}} \approx \sqrt{0.0106} \approx 0.103$ — a usable, non-vacuous bound despite the network potentially having millions of raw parameters, something a VC-dimension-based bound for the same network would likely fail to produce at all.

Worked example 2: an overfit posterior pays a much larger penalty

The same network, trained without regularization until it memorizes the training set, ends up with a posterior $Q'$ concentrated tightly around one idiosyncratic weight configuration far from the prior — $\text{KL}(Q'\|P) \approx 50{,}000$, a huge divergence, since a highly specific, memorized configuration is exponentially "surprising" relative to a broad prior. The penalty term becomes $\sqrt{2.5} \approx 1.58$ — larger than 1, making the bound on true error vacuous (worse than guessing), even though training error is lower than the regularized network's. The bound is directly penalizing the memorization.

Watch how far the posterior above shifts from the prior as more data arrives — a small, well-anchored shift is what keeps a PAC-Bayes bound tight; a large, idiosyncratic shift is exactly what it penalizes.

What this means in practice

PAC-Bayes is a leading framework for explaining why heavily overparameterized deep networks can still generalize well: their effective KL divergence from a sensible prior (often correlated with how much regularization, weight decay, or implicit bias toward flat minima was present during training) stays modest even though their raw parameter count is enormous. It also gives a formal argument for why starting training near a good prior (pretrained weights, sensible initialization, strong regularization) is not just a training-speed convenience — it's directly what keeps the generalization bound tight.