Expected PAC-Bayes Bounds for Bounded Losses

From Bounded Losses to an Expected Generalization Bound

A learning procedure can inspect the sample before choosing which predictors to emphasize. Consequently, a concentration statement for one predictor chosen in advance does not automatically apply to the predictor selected after seeing the data. The PAC-Bayes approach controls this adaptivity by comparing the data-dependent posterior to a prior fixed independently of the sample.

Here the target is an expectation bound: it limits the expected population risk of the posterior-averaged predictor in terms of its expected empirical risk and its expected divergence from the prior. Bounded losses make the concentration calculation especially direct.

Definition: Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$, and let $\mathcal H$ be a measurable hypothesis space. A measurable loss $\ell:\mathcal H\times\mathcal Z\to[0,1]$ defines the population risk and empirical risk $$ R(h)=E_{Z\sim P}[\ell(h,Z)],\qquad \widehat R_S(h)=\frac{1}{n}\sum_{i=1}^n \ell(h,Z_i), $$ where $S=(Z_1,\ldots,Z_n)$. For a probability distribution $\rho$ on $\mathcal H$, write $R(\rho)=\int R(h)\,\rho(dh)$ and $\widehat R_S(\rho)=\int\widehat R_S(h)\,\rho(dh)$. A posterior $\rho_S$ is a measurable probability kernel that may depend on $S$. A prior $\pi$ is a probability distribution on $\mathcal H$ fixed independently of $S$.

The posterior-averaged risk describes the performance of drawing $h$ from $\rho_S$ and evaluating that hypothesis. The theorem below also permits a randomized learning procedure: its risk quantities are averaged over the data, and the posterior itself is already integrated out in $R(\rho_S)$.

The Bounded-Loss Exponential-Moment Bound

The concentration ingredient is Hoeffding's lemma. Its boundedness assumption is what gives a quadratic exponential penalty, which will later become a term of order $1/n$ before optimization.

Lemma (Hoeffding's lemma): If a random variable $X$ takes values in an interval $[a,b]$, then, for every real $t$, $$ E\exp\bigl(t(X-E[X])\bigr)\leq \exp\left(\frac{t^2(b-a)^2}{8}\right). $$

Proof. Let $\phi(t)=\log E[\exp(t(X-E[X]))]$. Boundedness of $X$ permits differentiating its moment generating function twice. Under the exponentially tilted distribution, $\phi''(t)$ is the variance of $X$. Every distribution supported on $[a,b]$ has variance at most $(b-a)^2/4$: its variance is no greater than its mean squared distance from the midpoint, and that distance is at most $(b-a)/2$. Thus $\phi''(t)\leq(b-a)^2/4$. Also, $\phi(0)=\phi'(0)=0$. Taylor's formula with integral remainder gives $$ \phi(t)=t^2\int_0^1(1-u)\phi''(ut)\,du \leq \frac{t^2(b-a)^2}{4}\int_0^1(1-u)\,du =\frac{t^2(b-a)^2}{8}. $$ Exponentiating proves the claim. $\square$

For a fixed $h$, the losses $\ell(h,Z_i)$ are independent, have mean $R(h)$, and lie in $[0,1]$. Applying the lemma to each observation, with argument $-\lambda/n$, yields the following bound for any $\lambda>0$:

E_S\exp\left(\lambda\left[R(h)-\widehat R_S(h)\right]\right) \leq \exp\left(\frac{\lambda^2}{8n}\right).

Indeed, each centered loss contributes at most $\exp(\lambda^2/(8n^2))$; multiplying the $n$ bounds gives the displayed exponent. The hypothesis $h$ must be fixed in this calculation. The PAC-Bayes argument will use the prior to combine this fixed-hypothesis result with a posterior that can depend on the sample.

The Change-of-Measure Step

For probability distributions $\rho$ and $\pi$ with $\rho$ absolutely continuous with respect to $\pi$, define $$ \operatorname{KL}(\rho\Vert\pi) =\int \log\left(\frac{d\rho}{d\pi}\right)\,d\rho. $$ The change-of-measure inequality converts an integral under $\rho$ into an integral under $\pi$, at a cost measured by this divergence.

Change-of-measure inequality: If $\operatorname{KL}(\rho\Vert\pi)<\infty$ and $g$ is bounded and measurable, then $$ \int g\,d\rho \leq \operatorname{KL}(\rho\Vert\pi)+\log\int e^g\,d\pi. $$

To see why it holds, write $q=d\rho/d\pi$. Jensen's inequality for the concave logarithm gives $$ \int g\,d\rho-\operatorname{KL}(\rho\Vert\pi) =\int\log\left(\frac{e^g}{q}\right)d\rho \leq \log\int_{\{q>0\}}\frac{e^g}{q}\,d\rho \leq \log\int e^g\,d\pi. $$ The last inequality follows by substituting $d\rho=q\,d\pi$ on $\{q>0\}$. Boundedness of $g$ and finite divergence ensure the integrals used here are well defined.

Main Result: Expected PAC-Bayes Bound

Theorem: Suppose the observations are independent and identically distributed, $\ell$ is measurable and takes values in $[0,1]$, and $\pi$ is a prior fixed independently of the sample. Let $\rho_S$ be a measurable posterior such that $\rho_S$ is absolutely continuous with respect to $\pi$ almost surely and $$ E_S\left[\operatorname{KL}(\rho_S\Vert\pi)\right]<\infty. $$ Then, for every $\lambda>0$, $$ E_S[R(\rho_S)] \leq E_S[\widehat R_S(\rho_S)] +\frac{E_S[\operatorname{KL}(\rho_S\Vert\pi)]}{\lambda} +\frac{\lambda}{8n}. $$

Proof. For each realized sample $S$, apply the change-of-measure inequality with $\rho=\rho_S$ and $g(h)=\lambda(R(h)-\widehat R_S(h))$. Integrating $g$ under $\rho_S$ gives $$ \lambda\left[R(\rho_S)-\widehat R_S(\rho_S)\right] \leq \operatorname{KL}(\rho_S\Vert\pi) +\log\int \exp\left(\lambda[R(h)-\widehat R_S(h)]\right)\pi(dh). $$ Take expectation over $S$. By Jensen's inequality, the expectation of the logarithm is no greater than the logarithm of the expectation. Tonelli's theorem applies to the nonnegative exponential integrand, and the fixed-$h$ exponential-moment bound gives $$ E_S\int \exp\left(\lambda[R(h)-\widehat R_S(h)]\right)\pi(dh) =\int E_S\exp\left(\lambda[R(h)-\widehat R_S(h)]\right)\pi(dh) \leq \exp\left(\frac{\lambda^2}{8n}\right). $$ Therefore the expected logarithm is at most $\lambda^2/(8n)$. Taking expectations in the samplewise inequality and dividing by $\lambda$ proves the theorem. $\square$

The theorem requires no assumption that the posterior is independent of the sample. The prior, however, must be fixed independently of it. Its conclusion is about expectations over samples, not a guarantee that holds with a specified probability for each sample.

Choosing the Temperature and Reading the Penalty

Let $\kappa=E_S[\operatorname{KL}(\rho_S\Vert\pi)]$. The two added terms in the theorem trade off against each other: increasing $\lambda$ reduces $\kappa/\lambda$ but increases $\lambda/(8n)$. If $\kappa>0$, differentiating their sum gives the minimizing value $\lambda=\sqrt{8n\kappa}$. Substitution yields the consequence

Corollary: Under the theorem's assumptions, if $\kappa>0$, then $$ E_S[R(\rho_S)] \leq E_S[\widehat R_S(\rho_S)] +\sqrt{\frac{\kappa}{2n}}. $$ If $\kappa=0$, taking the infimum of the theorem's bound over $\lambda>0$ gives the same statement with zero added penalty.

For $\kappa>0$, the optimization is explicit: $$ \frac{\kappa}{\sqrt{8n\kappa}}+\frac{\sqrt{8n\kappa}}{8n} =2\sqrt{\frac{\kappa}{8n}} =\sqrt{\frac{\kappa}{2n}}. $$ Thus the optimized penalty decreases like $n^{-1/2}$ when the expected divergence is held fixed. A posterior closer to the prior, in expected KL divergence, pays a smaller penalty. This does not say that the empirical risk itself is small; the theorem bounds population risk by empirical risk plus a complexity term.

Worked Example: Computing a Finite-Space Complexity Penalty

Let $\mathcal H=\{h_1,h_2,h_3\}$, with prior $\pi=(0.5,0.3,0.2)$ and a fixed posterior $\rho=(0.2,0.5,0.3)$. Suppose the three population risks are $0.1,0.2,0.4$, respectively, and take $n=200$.

The posterior-to-prior divergence is $$ \begin{aligned} \operatorname{KL}(\rho\Vert\pi) &=0.2\log(0.2/0.5)+0.5\log(0.5/0.3)+0.3\log(0.3/0.2)\\ &=0.2\log(0.4)+0.5\log(5/3)+0.3\log(1.5)\\ &\approx -0.183258+0.255413+0.121639\\ &\approx 0.193794. \end{aligned} $$ The posterior population risk is $0.2(0.1)+0.5(0.2)+0.3(0.4)=0.24$. Since this posterior is fixed, linearity of expectation gives $E_S[\widehat R_S(\rho)]=R(\rho)=0.24$. The optimized penalty is $$ \sqrt{\frac{0.193794}{2(200)}}=\sqrt{0.000484485}\approx 0.0220. $$ Hence the theorem gives $E_S[R(\rho)]\leq 0.24+0.0220=0.2620$. The true risk is $0.24$; the upper bound is valid but not exact.

Worked Example: How Sample Size Changes the Bound

Consider two hypotheses, $a$ and $b$, and observations $Z_i\sim\operatorname{Bernoulli}(0.18)$. Set $\ell(a,z)=z$ and $\ell(b,z)=1-z$. Use the fixed posterior $\rho=\delta_a$ and prior $\pi(a)=e^{-0.8}$, $\pi(b)=1-e^{-0.8}$. Then $\operatorname{KL}(\rho\Vert\pi)=\log(1/\pi(a))=0.8$, and $E_S[\widehat R_S(\rho)]=R(a)=0.18$.

For $n=50$, the optimized penalty is $\sqrt{0.8/(2\cdot50)}=\sqrt{0.008}\approx0.08944$, so the bound is $E_S[R(\rho)]\leq0.26944$. For $n=200$, it is $\sqrt{0.8/(2\cdot200)}=\sqrt{0.002}\approx0.04472$, giving $E_S[R(\rho)]\leq0.22472$. The sample size quadruples, and the penalty halves, as the $n^{-1/2}$ rate predicts.

Worked Example: A Posterior That Adapts to the Sample

Let $Z\sim\operatorname{Bernoulli}(1/2)$, $n=1$, and $\mathcal H=\{h_0,h_1\}$, with prior assigning probability $1/2$ to each hypothesis. Define $\ell(h_0,z)=z$ and $\ell(h_1,z)=1-z$. After observing $Z$, choose $\rho_Z=\delta_{h_1}$ if $Z=0$, and $\rho_Z=\delta_{h_0}$ if $Z=1$.

In either case the chosen hypothesis has empirical risk zero. Each hypothesis has population risk $1/2$, so $R(\rho_Z)=1/2$ for both sample outcomes. Also, $\operatorname{KL}(\rho_Z\Vert\pi)=\log 2$ for either posterior. The optimized bound is therefore $$ E[R(\rho_Z)]\leq E[\widehat R_Z(\rho_Z)]+\sqrt{\frac{\log 2}{2}} =0+\sqrt{\frac{\log 2}{2}} \approx 0.5887. $$ The actual expected population risk is $0.5$, so the bound holds. This example shows why a data-dependent posterior can have zero observed loss yet incur a positive complexity penalty.

Common Mistake and Practical Meaning

Common mistake: “For every fixed hypothesis, the empirical risk is close to population risk. Therefore the same concentration bound applies to whichever hypothesis the algorithm selects from the sample.” The selection changes the problem: the selected hypothesis is not fixed independently of the observations, as the adaptive example illustrates.

Correction: First control exponential deviations for each fixed hypothesis, then integrate those deviations under the sample-independent prior. The change-of-measure inequality permits evaluation under the data-dependent posterior, charging the procedure according to $\operatorname{KL}(\rho_S\Vert\pi)$. Finally, averaging over samples gives an expected-risk statement. This argument does not provide a high-probability guarantee for an individual sample; that is a different form of PAC-Bayes result.

Key takeaway: For losses in $[0,1]$, an independent prior and a possibly sample-dependent posterior satisfy an expected population-risk bound with penalty $\sqrt{E_S[\operatorname{KL}(\rho_S\Vert\pi)]/(2n)}$. The prior provides the reference for measuring adaptivity; sample size and expected divergence jointly determine the penalty.

Check Your Understanding

Use the definitions and results above to answer these questions.

Which part of the theorem requires the prior to be fixed independently of the sample?
For a fixed posterior, why does the expected empirical risk equal the posterior population risk?
If the expected divergence stays fixed while sample size increases by a factor of nine, how does the optimized penalty change?
In the adaptive example, what are the expected empirical risk, population risk, and posterior-to-prior divergence?
Why does a fixed-hypothesis concentration bound alone not justify a bound for a hypothesis selected after observing the sample?