PAC-Bayes is the only generalization bound that has stayed within striking distance of empirical test error for modern neural networks. That alone makes it worth reading carefully. Below is the standard McAllester (1999) bound, with each piece unpacked.
Data: S = {(x_i, y_i)}_{i=1..n}, i.i.d. from distribution D
Hypotheses: H (e.g. all neural nets of a given architecture)
Loss: ℓ(h, x, y) ∈ [0, 1]
Empirical: R̂(h) = (1/n) Σ ℓ(h, x_i, y_i)
True: R(h) = E_{(x,y)~D} ℓ(h, x, y)
Classical PAC asks: how does R(h) relate to R̂(h) for the single hypothesis you pick? PAC-Bayes asks a different question: how does the expected R relate to the expected R̂ when you draw h from a distribution Q over hypotheses?
P: a "prior" distribution over H, chosen BEFORE seeing data
Q: a "posterior" distribution over H, allowed to depend on data
Two things to notice. First, P and Q are distributions over hypotheses, not over data — this is the move that confuses people coming from Bayesian inference, where the prior is over parameters and the posterior is over the same parameters given data. The notation is the same; the role is similar enough to share the words.
Second: P must be chosen before you see the training set. Q can be anything that depends on the training set. In practice, P is often a spherical Gaussian over weights, and Q is a Gaussian centered at the trained weights with some chosen variance.
With probability ≥ 1-δ over the draw of S, for all Q simultaneously:
E_{h~Q}[R(h)] ≤ E_{h~Q}[R̂(h)] + √( (KL(Q || P) + ln(2√n/δ)) / (2n) )
Read this slowly. The left side is the test loss you’d see if you sampled hypotheses from Q and averaged. The right side is two terms:
empirical_term = E_{h~Q}[R̂(h)] ← train loss, averaged over Q
complexity_term = √( (KL(Q||P) + ...) / (2n) )
The complexity term is what replaced VC dimension. Instead of “the hypothesis class is small,” the bound says “the posterior is close to the prior.” If Q is identical to P, the KL is zero and the bound collapses to the standard concentration bound on the prior’s expected risk. If Q has moved far from P to fit the data, you pay for the move in nats.
The clean derivation is in Dziugaite & Roy (2017). Their construction:
P = N(0, σ²·I) ← Gaussian prior over weights
Q = N(θ_trained, Σ_Q) ← Gaussian centered at SGD's output
The trick is choosing the variance of Q adaptively. Too small a variance, and you’ve effectively picked a single hypothesis — KL(Q||P) explodes. Too large, and E_{h~Q}[R̂(h)] explodes because you’re averaging in noisy hypotheses that no longer fit the training set. Optimize the variance to minimize the bound, and you find that the trained net sits in a wide-enough basin that you can spread Q across it without losing training accuracy. This is what makes the KL term manageable.
Dziugaite & Roy got non-vacuous bounds (≤ 0.20 test error) on MNIST classifiers — the first generalization bound on a real, non-toy network that didn’t trivially exceed one. The story is that flatness of the loss landscape, not parameter count, is what bounds generalize over.
The natural reading is the data-dependent prior line of work (Ambroladze, Catoni, more recent papers by Pérez-Ortiz). The idea is to use part of the data to learn P itself, then bound on the rest — and the bounds tighten further.