PAC-Bayes Oracle Inequalities

From a Generalization Bound to an Oracle Comparison

A PAC-Bayes deviation bound controls the risk of a posterior in terms of its empirical risk and its divergence from a prior. An oracle inequality adds a comparison: it shows that a particular learning rule performs nearly as well as a reference posterior, with a penalty for the reference posterior’s complexity. The reference need not be the posterior returned by the learning rule. It can represent a different candidate, or a distribution that concentrates on predictors with promising observed performance.

Here the learning rule is the empirical-risk Gibbs posterior. The key argument has two parts. A uniform PAC-Bayes bound controls the true risk of the learned posterior. A variational identity shows that this posterior minimizes empirical risk plus a KL penalty, so its penalized empirical criterion is no larger than the criterion of any reference posterior.

Definition: Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $D$. Let $\mathcal{H}$ be a measurable predictor space, and let $\ell(h,z)\in[0,1]$ be a jointly measurable loss. For a predictor $h$, define its risk and empirical risk by $$ R(h)=E_{Z\sim D}[\ell(h,Z)], \qquad \hat R(h)=\frac{1}{n}\sum_{i=1}^n \ell(h,Z_i). $$ For a probability distribution $Q$ on $\mathcal{H}$, write $R(Q)=E_{h\sim Q}[R(h)]$ and $\hat R(Q)=E_{h\sim Q}[\hat R(h)]$.

The prior $P$ is a probability distribution on $\mathcal{H}$ chosen independently of the sample. For distributions $Q$ and $P$, the KL divergence is $ \operatorname{KL}(Q\|P)=\int \log(dQ/dP)\,dQ $ when $Q$ is absolutely continuous with respect to $P$, and is infinite otherwise. A finite divergence therefore requires the posterior to put no mass outside the prior’s support.

The PAC-Bayes Deviation Bound

For any fixed $\lambda>0$, bounded losses give a simultaneous upper bound on the risk deviation of every posterior, including posteriors selected after seeing the data. The probability statement concerns the sample; on its high-probability event, the inequality holds for all $Q$ at once.

Theorem: Suppose the observations are independent and identically distributed, the loss is jointly measurable and takes values in $[0,1]$, and $P$ is a fixed prior independent of the sample. For fixed $\lambda>0$ and $\delta\in(0,1)$, with probability at least $1-\delta$, simultaneously for every posterior $Q$ with finite $\operatorname{KL}(Q\|P)$, $$ R(Q)\leq \hat R(Q)+ \frac{\operatorname{KL}(Q\|P)+\log(1/\delta)}{\lambda n} +\frac{\lambda}{8}. $$

For completeness, the proof uses Hoeffding’s lemma: if a random variable $Y$ lies in an interval of length $c$, then $ \log E[\exp(t(Y-E[Y]))]\leq t^2c^2/8 $ for every real $t$. One justification is to set $\psi(t)=\log E[\exp(tY)]$. Its second derivative is the variance under the exponentially tilted distribution. Every distribution supported on an interval of length $c$ has variance at most $c^2/4$: its squared distance from the interval midpoint is at most $c^2/4$, and variance is no greater than the mean squared distance from any fixed point. Thus $\psi''(t)\leq c^2/4$. Integrating twice from zero, using $\psi(0)=0$ and $\psi'(0)=E[Y]$, gives the stated lemma, for either sign of $t$.

To prove the theorem, first fix $h$. Apply Hoeffding’s lemma to each loss with $t=-\lambda$, and use independence:

E_{Z_1,\ldots,Z_n} \left[\exp\left\{\lambda n\big(R(h)-\hat R(h)\big)\right\}\right] \leq \exp\left(\frac{n\lambda^2}{8}\right).

Integrating over $h\sim P$ and using Tonelli’s theorem for the nonnegative integrand gives the same upper bound for $W=\int \exp\{\lambda n(R(h)-\hat R(h))\}\,dP(h)$. Markov’s inequality then implies that, with probability at least $1-\delta$, $ \log W\leq n\lambda^2/8+\log(1/\delta) $. On this event, apply the change-of-measure inequality $ E_Q[g]\leq\operatorname{KL}(Q\|P)+\log E_P[\exp(g)] $ to $g(h)=\lambda n(R(h)-\hat R(h))$. This inequality follows from Jensen’s inequality applied under $Q$ to $\exp(g)\,dP/dQ$; if the divergence is infinite, the desired bound is vacuous. Consequently,

\lambda n\big(R(Q)-\hat R(Q)\big) \leq \operatorname{KL}(Q\|P)+\log W \leq \operatorname{KL}(Q\|P)+\log(1/\delta)+\frac{n\lambda^2}{8}.

Dividing by $\lambda n$ proves the result. The single event constructed through $W$ does not depend on $Q$, which is why the inequality remains valid when $Q$ is chosen using the observed sample. $ \square $

The Gibbs Posterior and the Oracle Inequality

For a fixed $\lambda>0$, define the empirical-risk Gibbs posterior by exponentially downweighting predictors with larger empirical risk:

Definition: The empirical-risk Gibbs posterior $Q_\lambda$ has density with respect to $P$ $$ \frac{dQ_\lambda}{dP}(h) =\frac{\exp\{-\lambda n\hat R(h)\}}{Z_\lambda}, \qquad Z_\lambda=\int \exp\{-\lambda n\hat R(h)\}\,dP(h). $$ Because $0\leq\hat R(h)\leq1$, its normalizing constant satisfies $e^{-\lambda n}\leq Z_\lambda\leq1$, so it is finite and positive.

The defining density yields a variational identity. For any reference posterior $\rho$ with finite $\operatorname{KL}(\rho\|P)$, direct substitution gives

\operatorname{KL}(\rho\|Q_\lambda) = \operatorname{KL}(\rho\|P)+\lambda n\hat R(\rho)+\log Z_\lambda.

Since KL divergence is nonnegative, this identity shows that $Q_\lambda$ minimizes $ \hat R(Q)+\operatorname{KL}(Q\|P)/(\lambda n) $ over posteriors with finite divergence. More explicitly, applying the identity with $Q_\lambda$ itself gives equality in the minimum, while for any $\rho$ it gives

\hat R(Q_\lambda)+\frac{\operatorname{KL}(Q_\lambda\|P)}{\lambda n} \leq \hat R(\rho)+\frac{\operatorname{KL}(\rho\|P)}{\lambda n}.

Theorem: Under the assumptions of the PAC-Bayes deviation theorem, for fixed $\lambda>0$ and $\delta\in(0,1)$, with probability at least $1-\delta$, the Gibbs posterior satisfies, simultaneously for every reference posterior $\rho$ with finite $\operatorname{KL}(\rho\|P)$, $$ R(Q_\lambda)\leq \hat R(\rho)+ \frac{\operatorname{KL}(\rho\|P)+\log(1/\delta)}{\lambda n} +\frac{\lambda}{8}. $$

Proof. On the event of the PAC-Bayes deviation theorem, apply its bound to $Q_\lambda$:

R(Q_\lambda) \leq \hat R(Q_\lambda)+ \frac{\operatorname{KL}(Q_\lambda\|P)+\log(1/\delta)}{\lambda n} +\frac{\lambda}{8}.

The variational inequality bounds the empirical-risk-plus-divergence terms on the right by those of any $\rho$. Substitution gives the claimed oracle inequality. The event is uniform over all posteriors, so the same conclusion holds for all reference posteriors on that event, including a reference selected from the sample, provided the prior remains sample-independent and the reference has finite divergence. $ \square $

Worked Examples

Worked Example: Comparing Two Predictors

Suppose $\mathcal{H}=\{h_1,h_2\}$, $P(h_1)=P(h_2)=1/2$, and $n=100$. The observed empirical risks are $\hat R(h_1)=0.12$ and $\hat R(h_2)=0.30$. Use $\lambda=0.5$ and $\delta=0.05$. First calculate the Gibbs weights.

The unnormalized weights are $0.5e^{-50(0.12)}=0.5e^{-6}$ and $0.5e^{-50(0.30)}=0.5e^{-15}$. After cancelling the common factor, the posterior mass on $h_1$ is $1/(1+e^{-9})\approx0.999877$, and the mass on $h_2$ is approximately $0.000123$.

Take the reference posterior $\rho$ to put all its mass on $h_1$. Its empirical risk is $0.12$, and its divergence from the prior is $\operatorname{KL}(\rho\|P)=\log 2$. Since $\log(1/\delta)=\log 20$, the oracle inequality gives

R(Q_\lambda) \leq 0.12+\frac{\log 2+\log 20}{0.5(100)}+\frac{0.5}{8} =0.12+\frac{3.6889}{50}+0.0625 \approx0.2563.

This guarantee compares the learned posterior’s true risk with the reference’s observed risk, not with the unknown true risk of $h_1$. The divergence and confidence terms account for the price of making that comparison.

Worked Example: A Continuous Reference Posterior

Let $\mathcal{H}=[0,1]$, let $P$ be uniform on this interval, and let $\ell(\theta,z)=\theta$ for every observation $z$. Thus $R(\theta)=\hat R(\theta)=\theta$, regardless of the sample. Set $n=20$, $\lambda=1$, and $\delta=0.05$. Consider the reference posterior $\rho$ that is uniform on $[0,0.2]$.

The reference empirical risk is its mean, $\hat R(\rho)=0.1$. Its density is 5 on $[0,0.2]$ and zero elsewhere, whereas the prior density is 1 on $[0,1]$. Therefore

\operatorname{KL}(\rho\|P) =\int_0^{0.2}5\log(5)\,d\theta =\log 5.

The oracle bound is $0.1+(\log5+\log20)/20+1/8$. Because $\log5+\log20=\log100\approx4.6052$, the resulting upper bound is approximately $0.4553$. In this example the Gibbs density is $20e^{-20\theta}/(1-e^{-20})$. Its risk is its mean, $1/20-1/(e^{20}-1)\approx0.05$, consistent with the bound. A point mass at any fixed $\theta$ would have infinite KL divergence from the continuous uniform prior, but the interval-supported reference has finite divergence and can be used directly.

Worked Example: Choosing Among Three References

Suppose there are three predictors with prior probabilities $(0.80,0.15,0.05)$ and observed empirical risks $(0.18,0.10,0.04)$. Let $n=200$, $\lambda=0.4$, and $\delta=0.05$. A reference concentrated on predictor $j$ has divergence $\log(1/P(h_j))$. For the third predictor, the oracle bound is

0.04+\frac{\log20+\log20}{80}+\frac{0.4}{8} =0.04+\frac{5.9915}{80}+0.05 \approx0.1649.

For comparison, the corresponding bounds using the first and second predictors are, respectively, $0.18+(\log1.25+\log20)/80+0.05\approx0.2702$ and $0.10+(\log(1/0.15)+\log20)/80+0.05\approx0.2112$. Thus the third predictor gives the smallest of these three oracle bounds: its lower empirical risk compensates for its smaller prior probability.

The Gibbs weights are proportional to $0.80e^{-14.4}$, $0.15e^{-8}$, and $0.05e^{-3.2}$, since $\lambda n=80$. Their sum is approximately $0.0020889$, giving posterior probabilities approximately $(0.00021,0.0241,0.9757)$. The posterior concentrates on the third predictor, consistent with the reference comparison. The theorem also permits comparison with mixtures of predictors, not just these point-mass references.

Interpreting the Guarantee

The oracle inequality is useful because its right-hand side separates observed fit from complexity. A reference posterior with low empirical risk is attractive, but a reference that places substantial mass where the prior assigns very little probability pays a larger KL penalty. The statement can be summarized as an infimum over all finite-divergence references: the Gibbs posterior’s true risk is bounded by the best available reference trade-off, plus the confidence and temperature terms.

The parameter $\lambda$ affects both the posterior and the guarantee. A larger value makes the Gibbs posterior favor smaller empirical risks more strongly, while the bound’s complexity contribution decreases with $\lambda$ and its additive $\lambda/8$ term increases. The result requires $\lambda$ to be fixed for the stated probability guarantee; selecting it using the data requires a justification beyond this single fixed-$\lambda$ statement.

Common Pitfall

Wrong reasoning: “Because the reference posterior can be selected after seeing the sample, I can also choose a prior concentrated on whichever predictor looks best in that sample.” That changes the prior and invalidates the stated guarantee, whose proof integrates against a fixed, sample-independent $P$.
Correction: The reference posterior may be data-dependent because the event holds simultaneously for all posteriors. The prior may not be made data-dependent by this argument. A data-dependent prior needs a valid construction that controls information leakage, such as an independent sample split.
Another common error: Omitting the divergence term when comparing with a reference. A low empirical risk alone does not make a reference free: the inequality explicitly charges for its divergence from the prior.

Key takeaway: The Gibbs posterior minimizes empirical risk plus a KL penalty. Combining that variational property with a uniform PAC-Bayes deviation bound yields a high-probability oracle guarantee against every finite-divergence reference posterior.

Check Your Understanding

Use the definitions and results above to answer the following questions.

Why does the PAC-Bayes deviation event allow the reference posterior to depend on the observed sample?
For a reference with empirical risk $0.08$, KL divergence $1.2$, $n=100$, $\lambda=0.5$, and $\delta=0.05$, what numerical upper bound does the oracle inequality give?
Why can a point mass have infinite KL divergence from a continuous prior even when the point lies in the prior’s support?
In the Gibbs variational identity, which nonnegative quantity implies that the Gibbs posterior minimizes the penalized empirical criterion?
What assumption about the prior is needed for the stated high-probability guarantee, and why?

What You'll Learn