Posterior-Averaged Risk and Gibbs Prediction

Two Risks That Sound Similar

A PAC-Bayes guarantee often involves a posterior distribution \(Q\) over predictors. The risk in such a bound is averaged over that distribution: draw a predictor according to \(Q\), then average its population loss. A Gibbs prediction makes precisely such a random draw before predicting. This connects the PAC-Bayes quantity to a randomized prediction rule, but the connection is an expectation—not a guarantee that every predictor in the posterior performs well.

The distinction matters because the risk of a posterior draw is itself random. A posterior can put most of its mass on low-risk predictors and a small amount on high-risk ones, or it can spread its mass across predictors with similar risks. Both situations can have the same posterior-averaged risk but different probabilities of drawing a poor predictor. We will make these performance criteria precise and derive a bound for the average.

Posterior-Averaged Population and Empirical Risk

Let \(Z=(X,Y)\) be a test observation with distribution \(D\), and let \(h\) be a predictor from a measurable class \(\mathcal H\). Suppose the loss \(\ell(h,Z)\) is measurable and takes values in \([0,1]\). The population risk of a fixed predictor is its expected loss on a fresh observation. Given an independent training sample \(S=(Z_1,\ldots,Z_n)\) drawn identically from \(D\), its empirical risk is the average loss on that sample.

A posterior \(Q\) is a probability distribution over \(\mathcal H\); it may depend on the observed sample. Its posterior-averaged population and empirical risks are

These quantities average losses over predictors. In particular, \(R(Q)\) is an ordinary number once \(Q\) is fixed. By contrast, if \(H\sim Q\), then \(R(H)\) is a random variable: it is the population risk of the predictor actually drawn.

Why Gibbs Risk Equals Posterior-Averaged Risk

The equality follows from iterated expectation. The assumptions above ensure that the loss is measurable and bounded, so the expectations exist and the order of integration can be interchanged.

Proof. By the definition of the joint draw and Tonelli's theorem for a nonnegative loss (or Fubini's theorem when the loss is integrable),

Thus the posterior-averaged risk is exactly the expected test loss of a randomized Gibbs prediction. The equality does not say that the random variable \(R(H)\) equals its expectation for each draw. \(\square\)

A High-Probability PAC-Bayes Guarantee

The PAC-Bayes bound below makes the controlled quantity explicit. Let \(P\) be a prior distribution on \(\mathcal H\), fixed independently of the training sample. For probability measures \(Q\) and \(P\), \(\mathrm{KL}(Q\|P)\) is their Kullback–Leibler divergence; it is infinite unless \(Q\) is absolutely continuous with respect to \(P\). The bound holds simultaneously for all posteriors, including posteriors selected after seeing the sample.

The temperature \(\lambda\) in this version is fixed before observing the sample. The terms on the right are empirical posterior-averaged risk, a complexity and confidence penalty, and a bounded-loss concentration penalty.

Proof. For each fixed \(h\), Hoeffding's lemma applied to the independent, bounded losses gives

Integrate this inequality with respect to \(P\). Tonelli's theorem applies because the integrand is nonnegative, so

Markov's inequality therefore implies that, with probability at least \(1-\delta\), the integral inside the expectation is at most \(\exp\{\lambda^2/(8n)\}/\delta\). This is a single event depending on \(S\), not on \(Q\).

On that event, apply the change-of-measure inequality \(E_Q[g]\leq \mathrm{KL}(Q\|P)+\log E_P[e^g]\), valid for measurable \(g\) when the displayed expectations exist. With \(g(h)=\lambda(R(h)-\widehat R_S(h))\), this yields

If \(\mathrm{KL}(Q\|P)=\infty\), the stated bound is vacuous; otherwise divide by \(\lambda>0\). Since the event was uniform over \(Q\), the conclusion holds for every posterior on that event. \(\square\)

The theorem bounds \(R(Q)\), which the proposition identifies with the expected loss of a Gibbs prediction. It is not a bound on the risk of every predictor in the support of \(Q\), nor does it by itself bound the probability that one posterior draw has risk above a specified threshold.

Different Randomization Conventions, Same One-Case Risk

There are two common ways to use the randomness in a Gibbs rule. One can draw \(H\sim Q\) once and use that same predictor for many future observations. Or one can draw a fresh \(H\) independently for each prediction. In either case, for one fresh observation, the expected loss is \(R(Q)\). The conventions need not give the same dependence across a sequence of predictions: with one draw, the same predictor's strengths and weaknesses persist; with fresh draws, the predictor can change from case to case.

Common Pitfall: Replacing an Average by a Typical Draw

A small average risk does not automatically imply that most posterior draws have small risk. A useful general fact is Markov's inequality: for nonnegative \(R(H)\) and any \(t>0\), \(P_{H\sim Q}(R(H)\geq t)\leq R(Q)/t\). This can give a probability statement about a draw, but it is a separate, usually weaker conclusion and requires choosing a threshold \(t\).

For the two-classifier example above, the inequality at \(t=0.75\) gives an upper bound \(0.35/0.75\approx0.467\), while the actual probability of drawing a classifier with risk at least \(0.75\) is \(0.2\). Neither this inequality nor the PAC-Bayes bound claims that each draw is close to the average.

Another tempting substitution is to average the prediction values first and then evaluate the loss. That generally changes the object being evaluated. For example, let the response be \(Y=1\), and let \(Q\) put probability \(1/2\) on each of two constant regression predictors, \(h_0=0\) and \(h_2=2\). Under squared-error loss, each predictor has loss \(1\), so \(R(Q)=1\). A prediction equal to the arithmetic average, \(1\), has squared loss \(0\). These are different procedures and different criteria: the Gibbs rule samples one predictor, whereas averaging predictions produces a new prediction. The PAC-Bayes guarantee for \(R(Q)\) directly concerns the former.