PAC-Bayesian Setup: Priors, Posteriors, and Gibbs Risks

Why PAC-Bayes Needs Two Distributions

PAC-Bayesian analysis describes uncertainty about a predictor using a probability distribution on a predictor space. A prior represents a distribution chosen independently of the observed sample; a posterior may change after the sample is observed. This distinction lets us describe learning procedures that assign different weights to predictors in different data sets.

Before comparing any risks, it is important to say what is random. The sample is random, and a predictor drawn from its posterior is random conditional on that sample. A fresh test observation is another random quantity. Keeping these sources of randomness separate prevents a basic error: the empirical risk evaluated on the training sample is generally not an unbiased estimate of the population risk after the predictor has been selected using that sample.

Predictors, Data, and Measurability

Let $(\mathcal Z,\mathcal A)$ be a measurable data space, and let $P$ be the distribution of a new observation $Z$. In supervised learning, one may take $Z=(X,Y)$. Let $(\mathcal H,\mathcal G)$ be a measurable space of predictors, and let $\ell:\mathcal H\times\mathcal Z\to[0,1]$ be a jointly measurable loss. For a prediction rule $h$, $\ell(h,z)$ is its loss on observation $z$. The boundedness assumption is convenient here: it guarantees all the expectations below exist. Similar definitions apply to integrable nonnegative losses when the relevant integrals are finite.

Let $S=(Z_1,\ldots,Z_n)$ be a sample of independent observations, each with distribution $P$. The empirical risk of a fixed predictor is its average loss on this sample; its population risk is its expected loss on a new observation.

Definition: For $h\in\mathcal H$, define its population risk and empirical risk by $$ R(h)=\int_{\mathcal Z}\ell(h,z)\,P(dz), \qquad \widehat R_S(h)=\frac{1}{n}\sum_{i=1}^n\ell(h,Z_i). $$ The population risk averages over a new observation from $P$; the empirical risk averages over the realized training sample $S$.

Measurability is more than a technical decoration. Joint measurability of $\ell$ ensures that $R(h)$ is a measurable function of $h$, so it can itself be averaged over a distribution on predictors. It also ensures the empirical risk is measurable in the sample and predictor.

Prior and Posterior Distributions

A prior is a probability measure on $(\mathcal H,\mathcal G)$ fixed independently of the training sample. A posterior is a probability measure on the same space that may depend on the observed sample. To include this dependence precisely, the posterior is a probability kernel: for each sample $s$, $\rho_s$ is a probability measure on $\mathcal H$, and for each measurable set $A\in\mathcal G$, the map $s\mapsto\rho_s(A)$ is measurable.

Definition: A prior is a probability measure $\pi$ on $(\mathcal H,\mathcal G)$ chosen without using $S$. A posterior is a probability kernel $s\mapsto\rho_s$ from the sample space to $\mathcal H$. After observing $S=s$, a posterior draw $H$ has conditional distribution $\rho_s$.

The prior and posterior are distributions over predictors, not distributions over observations. The prior is fixed across samples; the posterior generally is not. For example, a posterior may put more weight on predictors that fit the observed data. That dependence is exactly why the posterior-averaged empirical risk and posterior-averaged population risk require careful distinction.

Worked Example: A Posterior That Selects the Matching Predictor

Let $Z\sim\operatorname{Bernoulli}(1/2)$, let $\mathcal H=\{h_0,h_1\}$ consist of the two constant binary predictors $h_j(z)=j$, and use zero-one loss $\ell(h,z)=\mathbf 1\{h(z)\ne z\}$. Take $n=1$. Define the posterior to put all its mass on the predictor that matches the observed label: $\rho_0=\delta_{h_0}$ and $\rho_1=\delta_{h_1}$.

Each fixed predictor has population risk $1/2$: $R(h_0)=P(Z=1)=1/2$ and $R(h_1)=P(Z=0)=1/2$. Thus every posterior draw has population risk $1/2$, and the posterior-averaged population risk is $1/2$.

In contrast, for either realized sample $S=z$, the posterior selects $h_z$, which has zero loss on $z$. Therefore $\widehat R_S(\rho_S)=0$ for both possible samples, and its expectation over samples is zero. The empirical and population quantities are not equal, even after averaging over the sample and the posterior draw.

Gibbs Risks

A posterior can be used to randomize over predictors: after seeing $S$, draw $H\sim\rho_S$, then evaluate that draw. Averaging the risk over the posterior gives the empirical and population Gibbs risks. The word “Gibbs” here indicates that the prediction rule is selected randomly from the distribution on predictors.

Definition: For a probability measure $\rho$ on $\mathcal H$, its population Gibbs risk is $$ R(\rho)=\int_{\mathcal H}R(h)\,\rho(dh). $$ For a realized sample $S$, its empirical Gibbs risk is $$ \widehat R_S(\rho)=\int_{\mathcal H}\widehat R_S(h)\,\rho(dh). $$ When $\rho=\rho_S$, both quantities depend on $S$; in particular, $\widehat R_S(\rho_S)$ uses the same sample to form the posterior and to evaluate empirical loss.

The notation $R(\rho_S)$ means an average of population risks over the posterior draw, not the risk of a deterministic “average predictor.” It can also be interpreted as expected loss when $H$ is drawn from $\rho_S$ and evaluated on a fresh observation independent of the sample and that draw.

Theorem: Suppose $Z_1,\ldots,Z_n$ are independent with distribution $P$, the loss is jointly measurable and bounded, and $s\mapsto\rho_s$ is a measurable probability kernel. Under the joint distribution that first draws $S$, then $H\mid S\sim\rho_S$, and independently draws $Z'\sim P$, $$ E_S[R(\rho_S)] = E_{S,H,Z'}[\ell(H,Z')]. $$ Also, $$ E_{S,H}[\widehat R_S(H)] = E_S[\widehat R_S(\rho_S)]. $$ These are separate identities; in general, their left-hand sides are not equal.

Proof. Since $\ell$ is bounded and jointly measurable, $R(h)=\int\ell(h,z')P(dz')$ is measurable in $h$, and all displayed integrals are finite. Integrating first over the independent fresh observation and then over the posterior draw gives $$ E_{S,H,Z'}[\ell(H,Z')] = \int P^n(ds)\int\rho_s(dh)\int P(dz')\,\ell(h,z'). $$ The inner integral over $z'$ is $R(h)$. The resulting expression is $$ \int P^n(ds)\int\rho_s(dh)\,R(h) = E_S[R(\rho_S)]. $$ For the empirical identity, condition on $S=s$. By the definition of the conditional distribution of $H$, $$ E[\widehat R_S(H)\mid S=s] = \int\widehat R_s(h)\,\rho_s(dh) = \widehat R_s(\rho_s). $$ Taking expectation over $S$ proves the second identity. Neither argument replaces the training observations inside $\widehat R_S$ with a fresh observation: doing so would incorrectly identify the two expectations. $\square$

What Independence Does—and Does Not—Give

For a fixed predictor $h$, each training observation has distribution $P$, so linearity of expectation gives $E_S[\widehat R_S(h)]=R(h)$. The same conclusion holds if a predictor is drawn from a fixed prior independently of the sample. It need not hold for a posterior that depends on that sample.

Result: If $H\sim\pi$ is drawn independently of $S$, then $$ E_{S,H}[\widehat R_S(H)] = E_H[R(H)]. $$ Indeed, conditioning on $H=h$, the sample is still distributed as $P^n$, so $E_S[\widehat R_S(h)]=R(h)$. Integrating this equality with respect to $\pi(dh)$ proves the result. If $H\mid S\sim\rho_S$, that independence argument is unavailable.

Worked Example: The Two Valid Expectations Can Differ

Keep the two constant predictors and zero-one loss, but now let $Z\sim\operatorname{Bernoulli}(1/4)$ and $n=1$. Use the posterior that assigns mass $0.8$ to the predictor matching the observed value and mass $0.2$ to the other predictor.

The fixed risks are $R(h_0)=1/4$ and $R(h_1)=3/4$. If $S=0$, the posterior mass on $h_0$ is $0.8$, so its posterior-averaged population risk is $$ R(\rho_0)=0.8(1/4)+0.2(3/4)=0.35. $$ If $S=1$, the posterior mass on $h_1$ is $0.8$, giving $$ R(\rho_1)=0.2(1/4)+0.8(3/4)=0.65. $$ Since $P(S=0)=3/4$ and $P(S=1)=1/4$, $$ E_S[R(\rho_S)]=(3/4)(0.35)+(1/4)(0.65)=0.425. $$

On either sample, the predictor matching that sample has zero empirical loss and the other has loss one. Thus $\widehat R_S(\rho_S)=0.2$ for both outcomes, so $E_S[\widehat R_S(\rho_S)]=0.2$. The difference, $0.425$ versus $0.2$, directly reflects the fact that the posterior favors the predictor matching the training observation. The fresh test observation in the population risk is not that training observation.

Randomized Prediction Is Not Necessarily a Mixture Predictor

A posterior draw can be used in at least two distinct ways. One may draw a predictor and incur its loss, then average that loss over the draw. Or, when the prediction space permits it, one may average the predictors’ output actions first and apply the loss to that averaged action. These are generally different procedures. The Gibbs risk defined here is the first: it averages losses over predictors.

Worked Example: Averaging Squared Loss After Randomization

Suppose the outcome is $y=0.2$, the action space is the real line, and the loss for action $a$ is $(a-y)^2$. Let the posterior put probability $1/2$ on each of two constant predictors that output $0$ and $1$.

If we draw a predictor and evaluate its loss, the posterior-averaged loss is $$ \frac12(0-0.2)^2+\frac12(1-0.2)^2 = \frac12(0.04)+\frac12(0.64) = 0.34. $$ If instead we first average the two actions, the resulting action is $0.5$, whose squared loss is $$ (0.5-0.2)^2=0.09. $$ The latter is the loss of an averaged-action predictor, not the Gibbs risk. In general, averaging a loss and applying a loss to an average are different operations.

Common Pitfall and Why the Distinction Matters

Incorrect reasoning: “For every fixed predictor, empirical risk averages to population risk. Therefore, averaging over a posterior preserves that equality.” The missing condition is independence. A sample-dependent posterior can give high weight to predictors precisely because they had low loss on that sample. Conditioning on the posterior draw does not restore the original sampling argument: the draw and the sample are associated.

Correction: State the two valid expectation identities separately. The expected population Gibbs risk equals the expected loss of a posterior draw on an independent fresh observation. The expected empirical Gibbs risk equals the expected empirical risk after averaging over the posterior conditioned on the same sample. Equating them requires additional assumptions or a separate argument; it is not a consequence of the definitions.

This bookkeeping is central to PAC-Bayesian analysis. Bounds will relate empirical and population Gibbs risks while accounting for how the posterior differs from the prior. At the setup stage, the essential discipline is to identify which distribution generates each quantity and whether the predictor distribution depends on the data being evaluated.

Check Your Understanding

Answer these by identifying the relevant distribution and source of randomness.

What makes a prior data-independent, and what measurability property is required of a sample-dependent posterior?
In $R(\rho_S)$, what is averaged over the posterior, and what distribution supplies the observation used to define each $R(h)$?
Why can $E_S[\widehat R_S(\rho_S)]$ differ from $E_S[R(\rho_S)]$? Give the role of the posterior’s dependence on $S$.
Under what condition does the expected empirical risk of a randomly drawn predictor equal its expected population risk?
For squared loss, why might the loss of a posterior-averaged action differ from the posterior-averaged loss?