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 . Classical PAC bounds control the worst case over a class. PAC-Bayes instead fixes a prior distribution over hypotheses before seeing the data, and then considers a posterior distribution that may depend on the data.
A randomised classifier drawn from works like this: for each prediction, sample and predict with that . Its true risk and empirical risk are averages over :
where is the population risk and 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 .
The McAllester bound
The most widely used PAC-Bayes bound, due to McAllester, says the following. For any prior fixed before seeing data, any , and any posterior , with probability at least over a training sample of size :
Read it term by term:
- is what you can measure. If the randomised classifier fits the training data well, this term is small.
- is the price of learning. If stays close to the prior , the price is small. If training drags the posterior far from the prior, the price grows.
- is the price of confidence. Demanding a smaller failure probability costs a little, but only logarithmically.
- The whole penalty shrinks like . 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 . Take a Gaussian prior and a Gaussian posterior . The KL divergence has a closed form. In dimensions:
Notice what each piece says. A large mean norm costs KL, because the posterior has moved far from a zero-centred prior. A very small posterior variance 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))
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 , the randomised rule. It does not directly bound a single draw from , 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 , and procedures that are stable under sampling tend to be the ones that generalise.
There is also a direct link to Bayesian practice. If is the Bayesian posterior for a likelihood and prior , then PAC-Bayes gives a frequentist certificate for that Bayesian procedure. If instead you choose 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)