Designing Priors for Predictor Classes

Why Prior Design Matters

A PAC-Bayes bound compares the empirical and population risks of a distribution $Q$ over predictors, while charging for how different $Q$ is from a reference prior $P$. The prior is therefore not just a technical ingredient: it determines which predictors are inexpensive to favor. A predictor assigned substantial prior mass can have a smaller complexity penalty than one assigned little mass.

The design principle is to assign mass before observing the sample, using information such as the predictor class, a complexity measure, or a coding scheme. The prior need not favor the predictor that ultimately performs best. Rather, it should make plausible, suitably simple predictors affordable while still being a genuine probability distribution. The posterior $Q$, by contrast, may be chosen after seeing the data.

Definition: Let $\mathcal H$ be a predictor class with a measurable structure. A prior $P$ is a probability measure on $\mathcal H$ fixed independently of the training sample. A posterior $Q$ is a probability measure on $\mathcal H$, possibly selected using that sample. When $Q$ is absolutely continuous with respect to $P$, their Kullback–Leibler divergence is $$ \operatorname{KL}(Q\|P)=\int_{\mathcal H}\log\!\left(\frac{dQ}{dP}(h)\right)\,dQ(h). $$ If $Q$ is not absolutely continuous with respect to $P$, define $\operatorname{KL}(Q\|P)=+\infty$.

For bounded loss $0\leq \ell(h,z)\leq 1$, write $R(h)=E[\ell(h,Z)]$ for the population risk and $\widehat R(h)$ for the empirical risk. Their posterior averages are $R(Q)=\int R(h)\,dQ(h)$ and $\widehat R(Q)=\int \widehat R(h)\,dQ(h)$. One standard high-probability PAC-Bayes-KL inequality states that, for i.i.d. data and any prior $P$ fixed independently of the sample, with probability at least $1-\delta$, simultaneously for every posterior $Q$,

\operatorname{kl}\!\left(\widehat R(Q)\,\middle\|\,R(Q)\right) \leq \frac{\operatorname{KL}(Q\|P)+\log(2\sqrt n/\delta)}{n},

where $\operatorname{kl}(u\|v)=u\log(u/v)+(1-u)\log((1-u)/(1-v))$ is Bernoulli KL divergence, with the usual limiting conventions at zero and one. Thus, for a fixed confidence level and sample size, the prior-dependent contribution is $\operatorname{KL}(Q\|P)$. This tutorial focuses on designing $P$ so that this contribution reflects predictor complexity.

Finite Classes: Mass Becomes a Logarithmic Penalty

Suppose $\mathcal H=\{h_1,\ldots,h_M\}$ is finite and $P(h_j)=p_j>0$. If the posterior puts all its mass on one predictor $h_j$, then its KL divergence from $P$ is exactly the negative log prior mass.

Result: For a finite predictor class and the point-mass posterior $Q=\delta_{h_j}$, $$ \operatorname{KL}(\delta_{h_j}\|P)=\log\frac{1}{P(h_j)}. $$ Consequently the predictor-specific contribution to the PAC-Bayes numerator is $\log(1/P(h_j))$.

To verify the identity, the density of $\delta_{h_j}$ with respect to $P$ at $h_j$ is $1/p_j$, and the posterior puts probability one there. Hence the defining KL sum has one nonzero term, $1\cdot\log(1/p_j)$. This calculation explains why prior mass has a logarithmic, rather than linear, effect on the penalty.

Worked Example: Redistributing Mass in a Four-Predictor Class

Consider four predictors and compare the uniform prior $P_U(h_j)=1/4$ with the nonuniform prior $P_N(h_1)=1/2$, $P_N(h_2)=1/4$, and $P_N(h_3)=P_N(h_4)=1/8$. The masses sum to one: $1/2+1/4+1/8+1/8=1$.

Under the uniform prior, each point-mass posterior has penalty $\log 4$. Under the nonuniform prior the four penalties are, respectively, $\log 2$, $\log 4$, $\log 8$, and $\log 8$. Thus $h_1$'s penalty is halved, since $\log 2=(1/2)\log 4$. Each of $h_3$ and $h_4$ has a penalty increased by $\log 2$; relative to the uniform penalty, the increase is $\log 8/\log 4=3/2$, or 50%, not a doubling. The prior shifts complexity cost from predictors it favors to those it favors less.

This comparison concerns only the complexity term. It does not say that $h_1$ has lower empirical or population risk. A prior can make a predictor cheaper to select; it cannot make that predictor more accurate.

A useful design rule is to start with a nonnegative complexity cost $c(h)$ and set $P(h)=\exp(-c(h))/Z$, where $Z=\sum_{g\in\mathcal H}\exp(-c(g))$ is finite and positive. Then $\log(1/P(h))=c(h)+\log Z$. The log normalizer is the cost of making the proposed weights a probability distribution. For a finite class, any real-valued costs give a finite positive normalizer. For an infinite class, summability must be checked.

Countable Classes: Complexity Costs and Codes

For a countable class $\mathcal H=\{h_1,h_2,\ldots\}$, a prior must still assign positive masses summing to one if point-mass posteriors are to have finite KL divergence. A complexity score alone is not enough: exponentiating its negative must produce summable weights. This is where code lengths provide a natural construction.

Worked Example: A Prior for Increasingly Complex Predictors

Suppose predictors are indexed by positive integers $k$, with larger $k$ indicating a more complex model. Set $P(h_k)=2^{-k}$. This is a probability distribution because $\sum_{k=1}^{\infty}2^{-k}=1$. The point-mass penalty for $h_k$ is $\log(1/P(h_k))=k\log 2$. In particular, the penalties for $k=1,2,3$ are $\log 2,\log 4,\log 8$.

Alternatively, suppose the desired penalty should grow roughly like $\log k$. The masses $P(h_k)=1/[k(k+1)]$ sum to one because $1/[k(k+1)]=1/k-1/(k+1)$, so the partial sum through $K$ is $1-1/(K+1)$, which tends to one. The penalty is $\log(k(k+1))$. At $k=10$, the mass is $1/110$, giving penalty $\log 110$. This is smaller than $10\log 2=\log 1024$ under the geometric prior, but the two priors encode different beliefs about how rapidly complexity should be penalized.

More generally, suppose nonnegative integer code lengths $L(h)$ satisfy the Kraft inequality $\sum_h 2^{-L(h)}\leq 1$. Let $S=\sum_h2^{-L(h)}$, which is positive when the class is nonempty, and define $P(h)=2^{-L(h)}/S$. This is a normalized prior and $\log(1/P(h))=L(h)\log 2+\log S\leq L(h)\log 2$, since $S\leq1$. Thus short descriptions receive more mass and pay smaller penalties. The prior is still fixed by the coding scheme, not by which predictor happens to fit the observed sample best.

Continuous Classes: Use Neighborhood Mass

A continuous class requires a different interpretation. If $P$ has a density on a continuous space, then every individual point typically has prior probability zero. A point-mass posterior $\delta_{h_*}$ is then not absolutely continuous with respect to $P$, so its KL divergence is infinite. Substituting a density value $p(h_*)$ for a point mass is not a valid fix: a density is not the probability assigned to that point.

Instead, one can consider a posterior supported on a region around a candidate. The following identity gives the exact cost when the posterior is the prior conditioned to that region.

Result: If $A\subseteq\mathcal H$ is measurable and $P(A)>0$, define the conditional prior $P_A(B)=P(B\cap A)/P(A)$. Then $$ \operatorname{KL}(P_A\|P)=\log\frac{1}{P(A)}. $$

Indeed, $dP_A/dP=1/P(A)$ on $A$ and zero outside $A$. Since $P_A$ assigns probability one to $A$, integrating the log density ratio gives $\int_A \log(1/P(A))\,dP_A=\log(1/P(A))$. This proves the identity and shows exactly how the prior probability of a neighborhood controls its PAC-Bayes cost.

Worked Example: Localizing a Uniform Prior on an Interval

Let the predictor be indexed by $h\in[0,1]$ and let $P$ be uniform on that interval. Choose the candidate $h_*=0.45$ and the neighborhood $A=[0.40,0.50]$. Its prior mass is its length, $P(A)=0.10$. For the posterior $Q=P_A$, the KL penalty is $\log(1/0.10)=\log 10$.

Suppose additionally that the population risk is $L$-Lipschitz in this index: for all $h,g\in[0,1]$, $|R(h)-R(g)|\leq L|h-g|$. Every $h\in A$ is at most $0.05$ from $h_*$, so $R(h)\leq R(h_*)+0.05L$. Averaging this inequality under $P_A$ gives $R(Q)\leq R(h_*)+0.05L$. Therefore the localized posterior pays complexity $\log 10$, while its population risk is at most $0.05L$ above that of the candidate. This is a neighborhood statement, not a finite penalty for the point mass at $h_*$.

The same calculation illustrates the dimension dependence. Let $P$ be uniform on $[0,1]^d$, and let $A$ be a cube of side length $2r$ fully contained in the parameter space, with $0<r\leq1/2$. Its mass is its volume, $P(A)=(2r)^d$, and conditioning on it costs $\log(1/P(A))=d\log(1/(2r))$. Smaller neighborhoods better localize the candidate but cost more KL; in higher dimension, a neighborhood of the same side length also has a larger penalty. This trade-off is an important part of prior design for continuous classes.

How to Design a Prior Before Seeing the Data

A useful design can be organized as a short sequence of choices. The goal is not to guess the eventual best predictor; it is to specify a defensible distribution over the class before using the training sample to select a posterior.

Specify the class and its structure.
Identify whether predictors form a finite set, a countable sequence, or a continuous space, and choose a meaningful complexity measure, index, or geometry.

Allocate mass using that structure.
For finite classes, assign positive weights; for countable classes, check that proposed weights sum to a finite value; for continuous classes, specify a probability measure with meaningful neighborhood probabilities.

Calculate the implied cost.
For a finite or countable candidate, compute $\log(1/P(h))$. For a continuous candidate, calculate the mass of an appropriate region and its log reciprocal.

Freeze the prior before sample-based selection.
Use the training data to choose $Q$ only after fixing $P$, unless a separate valid method handles data-dependent priors.

The final step is essential. If the same sample is used to inspect many possible priors and then select whichever gives the most favorable bound, the fixed-prior guarantee cannot simply be applied as though that selected prior had been fixed in advance. Prior constructions informed by the data require additional justification; they are not made valid merely by calling the selected distribution a prior.

Common Mistakes and Practical Interpretation

Confusing prior mass with a density. For a continuous prior, a density at $h_*$ is not $P(\{h_*\})$. Use the mass of a measurable neighborhood, or a posterior absolutely continuous with respect to the prior.
Forgetting normalization. Proposed weights are not a prior until they sum to one. In countable classes, verify summability and include the normalizing constant when calculating penalties.
Reading the penalty as a risk guarantee by itself. The prior contributes to the PAC-Bayes complexity term, but the bound also involves empirical risk, sample size, confidence, and the stated bounded-loss conditions.
Using the sample to choose an ordinary fixed prior. A prior selected after inspecting the same data is not independent of that data. A fixed-prior PAC-Bayes inequality does not automatically justify this choice.
Comparing penalties by the wrong ratio. Penalties are logarithms of inverse masses. In the four-predictor example, changing a mass from $1/4$ to $1/8$ adds $\log 2$; it changes the penalty from $\log 4$ to $\log 8$, a 50% increase, not a doubling.

Key takeaway: Prior design is the allocation of probability mass before data-driven posterior selection. A finite or countable candidate costs $\log(1/P(h))$; a continuous candidate is handled through the mass of a neighborhood. More prior mass means a smaller complexity penalty, but mass must be normalized and the prior must satisfy the independence conditions of the PAC-Bayes bound being used.

Check Your Understanding

Work through these questions by identifying the prior mass first, then translating it into a complexity cost.

A finite class has five predictors and a uniform prior. What is the point-mass KL penalty for selecting one predictor?
For a countable class with $P(h_k)=3/4^k$ for $k\geq1$, verify that the masses sum to one and calculate the penalty for $h_2$.
Why is a point-mass posterior generally assigned infinite KL divergence under a continuous prior with a density?
A continuous prior assigns probability $0.02$ to a neighborhood $A$. What is the KL divergence of the prior conditioned on $A$ from the original prior?
Explain why choosing a prior after inspecting the training sample is not covered automatically by a PAC-Bayes result for a prior fixed independently of that sample.