PAC-Bayesian Model Selection With Countable Priors

Why Countable Priors Make Model Complexity Explicit

When a candidate model is chosen after examining data, its empirical risk alone does not describe the strength of its generalization guarantee. A model that fit unusually well may have benefited from searching across many possibilities. A prior over models makes this search cost explicit: models assigned less prior mass pay a larger penalty.

For a countable family, the penalty has a direct interpretation as a code length. A short description receives relatively high prior mass and a smaller penalty; a long description receives low prior mass and a larger penalty. The resulting bound can be used to select a single model or to control a posterior distribution over models.

The prior must be fixed independently of the observations for the guarantee below. The model family itself may be large or countably infinite, but each candidate’s losses must be measurable and bounded in the stated range. The term \(C_j\) is small for a model given substantial prior mass and large for a model given little mass.

A Simultaneous Risk Bound for Every Candidate

The key benefit of a countable prior is that one high-probability event can cover every candidate, including a candidate selected after the data are observed. The following result uses Hoeffding’s inequality for each model and allocates the total error probability according to the prior.

Proof. Fix a candidate \(h_j\). Hoeffding’s inequality for the sample mean of independent \([0,1]\)-valued losses gives, for every \(\varepsilon>0\),

Set \(\varepsilon_j=\sqrt{\{\log(1/\pi_j)+\log(1/\delta)\}/(2n)}\). Substitution yields

The union bound applies to a countable collection of events, so the probability that any candidate violates its bound is at most

Consequently, with probability at least \(1-\delta\), none of the violations occurs. This proves the simultaneous claim. \(\square\)

Write the penalty as

The theorem says that empirical risk and prior complexity enter different parts of the same guarantee: \(\widehat R_j\) measures observed fit, while \(C_j\) measures how much prior probability the model received. Increasing \(n\) reduces the penalty; decreasing \(\pi_j\) increases it.

The Selection Guarantee and Its Proof

Define the penalized score \(S_j=\widehat R_j+\operatorname{pen}_j(\delta)\), and select a candidate with the smallest score. If a minimum is attained, call its index \(\widehat j\). On the event in the theorem, the chosen candidate satisfies \(R_{\widehat j}\leq S_{\widehat j}\). Since \(S_{\widehat j}\leq S_j\) for every \(j\), it follows that

This implication is deterministic once the simultaneous event holds: it combines the bound for the selected model with the definition of the selection rule. If the countable collection of scores has an infimum that is not attained, one can instead choose a candidate within any \(\eta>0\) of that infimum. Its risk is then at most \(\inf_j S_j+\eta\) on the same event.

Code Lengths and Posterior Distributions

A countable prior can encode a preference for simpler descriptions. If models have binary prefix-code lengths \(L_j\), Kraft’s inequality gives \(\sum_j 2^{-L_j}\leq1\). When this sum is \(Z>0\), define \(\pi_j=2^{-L_j}/Z\). Then

The code length therefore contributes directly to the complexity penalty, with lengths measured in bits converted to natural-log units by \(\log 2\). The normalizing term \(\log Z\) is common to all models. A normalized prior specified directly from a coding scheme is often the most convenient way to use this interpretation.

The simultaneous result also controls a posterior distribution \(\rho=(\rho_j)\) over the candidates, even if \(\rho\) depends on the observed data. Define \(R(\rho)=\sum_j\rho_jR_j\) and \(\widehat R(\rho)=\sum_j\rho_j\widehat R_j\). On the event where every candidate bound holds, multiplying each inequality by \(\rho_j\) and summing gives

This is a valid posterior guarantee, but it averages the candidate-specific penalties. It is not the same as replacing that average by a penalty involving \(\operatorname{KL}(\rho\|\pi)\). For that form, the PAC-Bayes-KL inequality gives, under the same bounded-loss and fixed-prior assumptions, with probability at least \(1-\delta\), simultaneously for all posterior distributions \(\rho\),

Here \(\operatorname{kl}(a\|b)=a\log(a/b)+(1-a)\log((1-a)/(1-b))\), with the usual continuous extension at the boundary, and \(\operatorname{KL}(\rho\|\pi)=\sum_j\rho_j\log(\rho_j/\pi_j)\). For a point mass on model \(j\), the posterior complexity is exactly \(\log(1/\pi_j)\). The KL form can be inverted to obtain a risk bound; the simpler Hoeffding bound above instead gives an immediately explicit square-root penalty.

Common Pitfall: Selecting Only by Empirical Risk

A tempting but incorrect argument is: “Model 4 has the lowest empirical risk, so it has the strongest generalization guarantee.” Empirical risk measures fit to the observed sample; it does not account for the possibility that a model received very little prior mass. The correction is to compare models using the risk bound, which includes \(\log(1/\pi_j)\), and then use the simultaneous event to justify the data-dependent selection.

A related error is to choose the prior after seeing which model performed best and then apply the fixed-prior guarantee as if nothing changed. The proof allocates failure probability using the prior weights before observing the sample. A prior chosen using data needs a separate valid construction; it cannot simply be substituted into this result.