DEV Community

Umesh Tharuka Malaviarachchi
Umesh Tharuka Malaviarachchi

Posted on

PAC-Bayes Bounds: Why a Prior Over Models Controls Generalisation

Most generalisation theory talks about a single model, or about a whole hypothesis class at once. PAC-Bayes theory sits in between, and that middle position is exactly why it is useful. It does not ask how many hypotheses exist. It asks how much you had to move away from a prior belief to reach the model you actually use.

The idea sounds Bayesian, and it borrows Bayesian language, but the guarantee is frequentist in flavour: with high probability over the training sample, the true risk of a randomised classifier is bounded by its empirical risk plus a penalty that depends on how far its posterior is from the prior. That penalty is measurable, computable, and often surprisingly informative.

From a single hypothesis to a distribution over hypotheses

Fix a loss bounded between 0 and 1, for example 0-1 loss or a scaled squared loss. Let a hypothesis be denoted by hh . Classical PAC bounds control the worst case over a class. PAC-Bayes instead fixes a prior distribution PP over hypotheses before seeing the data, and then considers a posterior distribution QQ that may depend on the data.

A randomised classifier drawn from QQ works like this: for each prediction, sample h∼Qh \sim Q and predict with that hh . Its true risk and empirical risk are averages over QQ :

R(Q)=Eh∼Q[R(h)],R^(Q)=Eh∼Q[R^(h)] R(Q) = \mathbb{E}{h \sim Q}[R(h)], \quad \hat{R}(Q) = \mathbb{E}{h \sim Q}[\hat{R}(h)]

where R(h)R(h) is the population risk and R^(h)\hat{R}(h) is the training risk.

This averaging step is doing real work. A posterior that concentrates on one sharp minimum and a posterior that spreads over a flat region can have the same average training loss but very different generalisation behaviour. PAC-Bayes makes that difference explicit through the Kullback-Leibler divergence KL(Q∣P)\mathrm{KL}(Q | P) .

The McAllester bound

The most widely used PAC-Bayes bound, due to McAllester, says the following. For any prior PP fixed before seeing data, any δ∈(0,1)\delta \in (0, 1) , and any posterior QQ , with probability at least 1−δ1 - \delta over a training sample of size nn :

R(Q)≤R^(Q)+KL(Q∣P)+log⁡2nδ2n R(Q) \leq \hat{R}(Q) + \sqrt{\frac{\mathrm{KL}(Q | P) + \log\frac{2\sqrt{n}}{\delta}}{2n}}

Read it term by term:

  • R^(Q)\hat{R}(Q) is what you can measure. If the randomised classifier fits the training data well, this term is small.
  • KL(Q∣P)\mathrm{KL}(Q | P) is the price of learning. If QQ stays close to the prior PP , the price is small. If training drags the posterior far from the prior, the price grows.
  • log⁡2nδ\log\frac{2\sqrt{n}}{\delta} is the price of confidence. Demanding a smaller failure probability δ\delta costs a little, but only logarithmically.
  • The whole penalty shrinks like 1/n1/\sqrt{n} . More data forgives a larger move away from the prior.

There is no term for the size of the hypothesis class. A class can be infinite, even uncountably infinite, and the bound still applies, provided the prior and posterior are well defined and the KL term is finite. That is a genuine advantage over uniform bounds based on VC dimension or covering numbers, which can be vacuous for large neural networks.

Why the prior matters so much

The prior is not a statement about what you believe before training in some deep philosophical sense. In the bound, it is a reference distribution. The KL term measures complexity relative to that reference.

This has two practical consequences.

First, a good prior makes the bound tighter. If the prior already puts mass near good solutions, then a posterior that concentrates there pays a small KL price. This is why data-dependent priors are so attractive: split the data, learn a prior on one part, and apply the bound on the rest. The prior is still fixed before the data used in the bound is seen, so the theorem holds, but the prior is now informed rather than arbitrary.

Second, a bad prior can make the bound vacuous. If the prior puts almost no mass where the posterior needs to go, the KL term explodes and the right hand side exceeds 1, which tells you nothing for a loss bounded by 1. A vacuous bound is not a false statement. It is an empty one. PAC-Bayes does not promise a tight bound for every prior. It promises a valid bound for every prior, and tightness is something you have to earn by choosing well.

A useful mental model: the prior is a compression scheme. Learning is cheap when the learned model can be described briefly relative to the prior, and expensive when it cannot. PAC-Bayes formalises that intuition through KL divergence rather than through code length, but the spirit is the same.

A concrete case: Gaussian prior and posterior over weights

Consider linear models, or the last layer of a network, with weight vector ww . Take a Gaussian prior P=N(0,σ02I)P = \mathcal{N}(0, \sigma_0^2 I) and a Gaussian posterior Q=N(μ,σ2I)Q = \mathcal{N}(\mu, \sigma^2 I) . The KL divergence has a closed form. In dd dimensions:

KL(Q∣P)=12(dσ2+∣μ∣2σ02−d+dlog⁡σ02σ2) \mathrm{KL}(Q | P) = \frac{1}{2} \left( \frac{d\sigma^2 + |\mu|^2}{\sigma_0^2} - d + d \log\frac{\sigma_0^2}{\sigma^2} \right)

Notice what each piece says. A large mean norm ∣μ∣2|\mu|^2 costs KL, because the posterior has moved far from a zero-centred prior. A very small posterior variance σ2\sigma^2 also costs KL, because concentrating sharply is an informative claim that needs evidence. A posterior that keeps some spread pays less, which is one way PAC-Bayes captures the flat minima intuition: flat regions admit spread-out posteriors with low training risk and moderate KL, while sharp minima force either high variance (and higher training risk) or sharp concentration (and high KL).

The following snippet computes the bound for this Gaussian case. It is a direct implementation of the formula above, not a claim about any real dataset.

import math

def pac_bayes_bound(empirical_risk, kl, n, delta=0.05):
    penalty = math.sqrt((kl + math.log(2 * math.sqrt(n) / delta)) / (2 * n))
    return empirical_risk + penalty

def gaussian_kl(mu_norm_sq, sigma, sigma0, d):
    return 0.5 * (
        (d * sigma**2 + mu_norm_sq) / sigma0**2
        - d
        + d * math.log(sigma0**2 / sigma**2)
    )

# Illustrative numbers only: 10,000 examples, a moderate move from the prior
kl = gaussian_kl(mu_norm_sq=25.0, sigma=0.1, sigma0=1.0, d=100)
print("KL:", round(kl, 1))
print("Bound:", round(pac_bayes_bound(0.10, kl, n=10000), 3))
Enter fullscreen mode Exit fullscreen mode

With these illustrative numbers, the KL term is large enough that the bound is loose, which is itself the lesson: a posterior mean of norm 5 in 100 dimensions, concentrated at scale 0.1 against a unit prior, is a strong claim, and the bound charges for it. Shrinking the mean, widening the posterior, or using a prior centred closer to the solution all reduce the charge. That trade-off is visible in the formula before any experiment is run.

PAC-Bayes and the Gibbs classifier

A common confusion is between the randomised Gibbs classifier and a deterministic model. The bound above applies to QQ , the randomised rule. It does not directly bound a single draw from QQ , nor does it bound the posterior mean as a deterministic predictor.

In practice, there are standard ways to bridge the gap. One route bounds the deterministic majority vote of the Gibbs classifier, at the cost of a factor of 2 in the simplest version. Another route uses a derandomisation argument for specific model classes. The key point for a practitioner is not to quote the Gibbs bound as if it were a bound on the single model you deploy, without saying which bridge you used. The randomised bound is still valuable: it certifies a procedure, namely sampling from QQ , and procedures that are stable under sampling tend to be the ones that generalise.

There is also a direct link to Bayesian practice. If QQ is the Bayesian posterior for a likelihood and prior PP , then PAC-Bayes gives a frequentist certificate for that Bayesian procedure. If instead you choose QQ by minimising the bound itself, that is, by trading empirical risk against KL, you get a learning algorithm: PAC-Bayes-inspired training. This is closely related to variational inference, where the evidence lower bound trades a data fit term against exactly the same KL term. The objectives rhyme because they encode the same tension between fitting and staying close to a reference.

Limitations and common pitfalls

PAC-Bayes bounds are valid, but validity is a low bar. Watch for these failure modes.

Vacuous bounds. A bound above 1 for 0-1 loss says nothing. This is common with uninformative priors and sharp posteriors on neural networks. Reporting a vacuous bound as if it were evidence of generalisation is a category error.

The prior must be data-free for the bound data. You cannot fit the prior on the same data and then apply the bound to that data without adjusting the argument. Data-dependent priors are allowed, but only through a clean split or a union bound over a countable set of candidate priors. Ignoring this step invalidates the certificate.

Randomised versus deterministic. As above, the bound certifies the Gibbs classifier. Quoting it for a single deterministic network without a derandomisation step overstates what was proved.

KL is not the whole story. Two posteriors can have the same KL and very different empirical risk, and two models can have the same bound but different robustness, calibration, or behaviour under shift. PAC-Bayes says nothing about distribution shift, because the population risk is defined with respect to the same distribution that generated the training data.

Optimising the bound is not the same as optimising accuracy. A posterior that minimises the bound may sacrifice some training accuracy to buy a much smaller KL term. That is often a good trade, but it is a trade, and it should be evaluated on held-out data like any other regularisation choice.

When to reach for PAC-Bayes

PAC-Bayes is most useful when the hypothesis class is too large for uniform bounds, when you have a sensible prior (from pretraining, from a data split, or from domain knowledge), and when you care about a certificate for a randomised procedure rather than a worst-case guarantee over a class. It is less useful when you need a tight bound for a single deterministic model, when no good prior is available, or when the real risk is distribution shift rather than sampling variation.

Used well, it reframes generalisation as a question with a computable answer: how much did you have to move from your starting point to fit the data, and was that move worth it? The bound does not answer that question for you. It prices it, and pricing it honestly is often the most useful thing theory can do.

Takeaway

A PAC-Bayes bound controls the true risk of a randomised classifier by its training risk plus a penalty proportional to the KL divergence from a fixed prior. A good prior, a spread-out posterior, and enough data make that penalty small. A bad prior or an over-concentrated posterior make it vacuous. The value of the theory is not that it always gives a tight number, but that it names the exact trade-off that learning has to navigate: fit the data, but do not move further from your starting point than the data justifies.


Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial

Top comments (0)