PAC–Bayes KL Risk Certificate

Worked Example

Consider a hypothesis space of three classifiers, with a uniform data-independent prior P = [1/3, 1/3, 1/3]. Suppose we select a "Good" posterior distribution Q = [0.8, 0.1, 0.1] after observing training errors from a "Mixed" empirical profile [0, 0.1, 0.3] on 100 samples with a failure probability δ = 0.05. The independent calculations are:

1. Empirical Gibbs Loss: The expected loss under Q is 0.8×0 + 0.1×0.1 + 0.1×0.3 = 0.01 + 0.03 = 0.04.
2. Posterior-Prior KL Divergence: KL(Q||P) = 0.8×ln(0.8 / (1/3)) + 0.1×ln(0.1 / (1/3)) + 0.1×ln(0.1 / (1/3)) ≈ 0.45958.
3. Bernoulli KL Budget: The total risk allowance is (KL(Q||P) + ln(2×√100 / 0.05)) / 100. With ln(400) ≈ 5.99146, the budget is (0.45958 + 5.99146) / 100 ≈ 0.06451.
4. PAC-Bayes Upper Risk: We find the upper true risk p ∈ [0.04, 1] such that kl(0.04 || p) = 0.06451. By numerically solving this, we get p ≈ 0.15063, which guarantees with 95% confidence that the true risk will not exceed 15.06%.

Experiment

You can verify how changing the complexity of the posterior distribution and the size of the training dataset affects the risk budget and upper risk bound using the interactive PAC–Bayes KL Risk Certificate module.

1. Select the Posterior control and change it from "Good" to "Point" (which concentrates all mass on a single hypothesis).
2. Observe that the Posterior prior KL increases from 0.459 to 1.098, reflecting a higher complexity penalty for drastically shifting away from the uniform prior.
3. Change the Training errors to "Wrong". The Empirical Gibbs loss instantly jumps to 1, and consequently, the PAC Bayes upper risk hits the ceiling at 1.
4. Change the Sample size from 100 to 200. Observe the Bernoulli KL budget decrease as more data reduces the uncertainty, tightening the upper risk bound closer to the empirical loss.

Limitations

The PAC-Bayes KL theorem assumes the training data is independently and identically distributed (i.i.d.). The prior distribution P must be chosen before seeing the training data used to evaluate the empirical errors; fitting the prior to the data invalidates the bound. Additionally, this certificate applies strictly to the Gibbs classifier (a stochastic hypothesis drawn according to Q on each prediction), not the deterministic majority vote, which requires different bounds (like the C-bound). When the empirical error is exactly 1 (as in the "Wrong" boundary case), the upper risk bound trivially becomes 1, providing no useful generalization guarantee.

References

The theorem and its derivation based on the Kullback-Leibler divergence between Bernoulli distributions are detailed in the foundational paper PAC-Bayesian Generalization Error Bounds for Gaussian Process Classification by Seeger (2002). For a broader exploration of PAC-Bayesian theory and its various complexity measures, see PAC-Bayesian Learning of Linear Classifiers by Langford (2005), which discusses inversion bounds.