PAC-Bayes Bounds Through Mutual Information

Why Mutual Information Enters a Generalization Bound

A predictor can fit its training sample well because it has learned a real pattern, or because its choice was influenced by idiosyncrasies of that particular sample. Mutual information quantifies how much observing the sample tells us about the predictor selected by a learning algorithm. This makes it a natural measure of how strongly the algorithm can adapt to its data.

In PAC-Bayesian analysis, a learning algorithm often returns a posterior distribution over predictors, rather than a single predictor. The expected Kullback–Leibler divergence of this posterior from a fixed prior is a familiar measure of adaptation. The key connection here is that this expected divergence contains two parts: information the predictor carries about the sample, and divergence of the predictor's marginal distribution from the prior.

Setup and Definitions

Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $D$, and write $S=(Z_1,\ldots,Z_n)$. Let $\mathcal W$ be a measurable predictor space, and let $\ell:\mathcal W\times\mathcal Z\to[0,1]$ be a measurable loss. For a predictor $w$, define its risk and empirical risk by

R(w)=E_{Z\sim D}[\ell(w,Z)], \qquad \widehat R_S(w)=\frac{1}{n}\sum_{i=1}^n \ell(w,Z_i).

A randomized learning algorithm is described by a probability kernel $Q_S$ on $\mathcal W$: after observing $S$, it draws a predictor $W$ according to $Q_S$. Write $\overline Q$ for the marginal distribution of $W$, averaging over both the random sample and the algorithm's randomization. Throughout, a prior $P$ is a fixed distribution on $\mathcal W$, chosen independently of $S$.

Definition: The mutual information between $S$ and $W$ is $$ I(S;W)=\operatorname{KL}\!\left(\mathcal L(S,W)\,\middle\|\,\mathcal L(S)\otimes\overline Q\right). $$ Here $\mathcal L(S,W)$ is their joint distribution, $\mathcal L(S)\otimes\overline Q$ is the distribution that makes them independent while preserving their marginals, and $\operatorname{KL}(A\|B)$ denotes relative entropy. When conditional distributions are available, $I(S;W)=E_S[\operatorname{KL}(Q_S\|\overline Q)]$.

Thus, $I(S;W)=0$ precisely when $S$ and $W$ are independent. A large value indicates that learning the sample can substantially change the distribution of the selected predictor. Mutual information is measured in nats when natural logarithms are used.

Expected Posterior-to-Prior Divergence

The connection to a PAC-Bayesian prior follows from the chain rule for relative entropy. Suppose $Q_S\ll P$ for almost every sample and $E_S[\operatorname{KL}(Q_S\|P)]<\infty$. Then $\overline Q\ll P$, and

E_S[\operatorname{KL}(Q_S\|P)] = I(S;W)+\operatorname{KL}(\overline Q\|P).

The first term measures dependence between the data and the randomized predictor. The second measures how far the predictor's overall marginal distribution is from the prior. Both are nonnegative, so mutual information is no larger than the expected posterior-to-prior divergence.

Result: Under the stated absolute-continuity and finiteness conditions, $$ I(S;W)\leq E_S[\operatorname{KL}(Q_S\|P)]. $$ Equality holds when $\overline Q=P$.

To see the decomposition, let $q_s(w)$, $\bar q(w)$, and $p(w)$ denote densities of $Q_s$, $\overline Q$, and $P$ with respect to a common dominating measure. The joint law of $(S,W)$ has density $q_s(w)$ relative to $\mathcal L(S)$ times that measure. In the mutual information integral, the density ratio is $q_s(w)/\bar q(w)$. In the expected posterior-to-prior integral, it is $q_s(w)/p(w)$. Wherever $q_s(w)>0$, split the logarithm:

\log\frac{q_s(w)}{p(w)} = \log\frac{q_s(w)}{\bar q(w)} + \log\frac{\bar q(w)}{p(w)}.

Integrating the first term over the joint law gives $I(S;W)$. Integrating the second term first over $Q_s$ and then over $S$ gives its integral under $\overline Q$, namely $\operatorname{KL}(\overline Q\|P)$. The assumed finiteness ensures these quantities are well-defined and the identity applies.

Worked Example: A Deterministic Predictor Copies One Observation

Let $n=1$, let $Z$ be Bernoulli with $P(Z=0)=P(Z=1)=1/2$, and let predictors be $w\in\{0,1\}$. Use the loss $\ell(w,z)=\mathbf 1\{w\ne z\}$. Suppose the algorithm sets $W=Z$.

For either fixed predictor, the risk is $R(w)=1/2$. The empirical risk of the selected predictor is $\widehat R_S(W)=0$, so the expected generalization gap is $1/2-0=1/2$.

The marginal law of $W$ is uniform, and $W$ is a deterministic copy of $S=Z$. Hence $H(W)=\log 2$, $H(W\mid S)=0$, and $I(S;W)=\log 2$. Taking $P$ to be uniform also gives $\operatorname{KL}(Q_S\|P)=\log 2$ for each sample, since $Q_S$ is a point mass on one of two equally likely predictors. The mutual-information bound below is $\sqrt{\log(2)/2}$, approximately $0.589$, which is larger than the actual gap $0.5$.

An Expected Generalization Bound

The mutual-information bound follows by combining a change-of-measure inequality with concentration for a fixed predictor. Define the signed generalization gap

g(S,w)=R(w)-\widehat R_S(w).

For each fixed $w$, the observations are independent and the losses lie in $[0,1]$. Hoeffding's lemma therefore gives, for every real $\lambda$,

E_S\!\left[\exp\{\lambda g(S,w)\}\right] \leq \exp\!\left(\frac{\lambda^2}{8n}\right).

The same bound holds with $g$ replaced by $-g$. Integrating over $w\sim\overline Q$ preserves the bound because it holds for every fixed $w$.

Theorem: Suppose $S\sim D^n$, the observations are independent, the loss is measurable and lies in $[0,1]$, and $W$ is drawn from a measurable kernel $Q_S$. If $I(S;W)<\infty$, then $$ \left|E_{S,W}\!\left[R(W)-\widehat R_S(W)\right]\right| \leq \sqrt{\frac{I(S;W)}{2n}}. $$ If, in addition, $Q_S\ll P$ almost surely for a fixed prior $P$ independent of $S$, with finite expected divergence, then $$ \left|E_{S,W}\!\left[R(W)-\widehat R_S(W)\right]\right| \leq \sqrt{\frac{E_S[\operatorname{KL}(Q_S\|P)]}{2n}}. $$

For completeness, the change-of-measure inequality used in the proof is the following: for probability measures $A\ll B$, a bounded measurable function $h$, and finite $\operatorname{KL}(A\|B)$,

E_A[h]\leq \operatorname{KL}(A\|B)+\log E_B[e^h].

Indeed, define the tilted probability measure $B_h$ by its density $e^h/E_B[e^h]$ relative to $B$. Nonnegativity of relative entropy gives $0\leq\operatorname{KL}(A\|B_h)=\operatorname{KL}(A\|B)-E_A[h]+\log E_B[e^h]$, which rearranges to the claimed inequality.

Apply this inequality with $A=\mathcal L(S,W)$, $B=\mathcal L(S)\otimes\overline Q$, and $h(S,W)=\lambda g(S,W)$, where $\lambda>0$. By definition, $\operatorname{KL}(A\|B)=I(S;W)$. Under $B$, $S$ and $W$ are independent; integrating the fixed-$w$ Hoeffding bound over $w\sim\overline Q$ yields

E_A[g(S,W)] \leq \frac{I(S;W)}{\lambda}+\frac{\lambda}{8n}.

If $I(S;W)>0$, the right-hand side is minimized at $\lambda=\sqrt{8nI(S;W)}$, giving $\sqrt{I(S;W)/(2n)}$. When $I(S;W)=0$, taking $\lambda$ down to zero gives an upper bound of zero. Applying the same argument to $-g$ bounds $-E_A[g]$ by the same quantity, and together these two inequalities bound the absolute value. Finally, the relative-entropy decomposition gives $I(S;W)\leq E_S[\operatorname{KL}(Q_S\|P)]$, which proves the prior-based version. $\square$

Worked Example: Adding Noise to a Data-Dependent Choice

Keep the binary distribution and loss from the preceding example, with $n=1$, but now let the algorithm output $W=Z$ with probability $0.9$ and $W=1-Z$ with probability $0.1$. The marginal distribution of $W$ remains uniform.

For either predictor, the risk is $1/2$. The expected empirical risk is the probability that $W\ne Z$, which is $0.1$. Therefore the expected generalization gap is $0.5-0.1=0.4$.

Let $h(\varepsilon)=-\varepsilon\log\varepsilon-(1-\varepsilon)\log(1-\varepsilon)$ denote binary entropy. Here $H(W)=\log 2$ and $H(W\mid S)=h(0.1)$, so

I(S;W)=\log 2-h(0.1) \approx 0.693147-0.325083 =0.368064.

The bound is $\sqrt{0.368064/2}\approx 0.429$, which exceeds the actual gap $0.4$. For the uniform prior, the expected posterior-to-prior divergence is also $0.368064$, because the posterior distribution given either sample has probabilities $0.9$ and $0.1$, while its marginal is uniform.

When Mutual Information Improves on the Prior Divergence

The expected posterior-to-prior divergence can charge for a mismatch that has nothing to do with adapting to the observed sample. Mutual information removes this marginal mismatch. For a sample-independent algorithm, $Q_S=\overline Q$ for every $S$, so $I(S;W)=0$, even if $\overline Q$ is far from the chosen prior. Its expected generalization gap is zero: independence gives $E[\widehat R_S(W)]=E[R(W)]$.

Worked Example: A Sample-Independent Predictor Distribution

Suppose the predictor space is $\{0,1\}$, and an algorithm always draws $W=1$ with probability $0.8$, independently of the sample. Let the fixed prior assign probability $0.5$ to each predictor. Since $W$ does not depend on $S$, $I(S;W)=0$.

The posterior is the same distribution for every sample, so its divergence from the prior is

\operatorname{KL}(\overline Q\|P) =0.8\log\frac{0.8}{0.5} +0.2\log\frac{0.2}{0.5} \approx 0.376003-0.183258 =0.192745.

The decomposition reads $0.192745=0+0.192745$: all the expected posterior-to-prior divergence is marginal mismatch, not information about the sample. The mutual-information bound gives an expected gap of zero, while the prior-based bound is positive. The zero expected gap is consistent with sample independence, though it does not say that every realized sample has zero gap.

Interpretation and Common Pitfall

This is an expected bound: it controls the absolute value of the average signed gap over both the sample and the algorithm's randomization. It is not, by itself, a claim that the gap is small with high probability for every realized sample or every predictor drawn by the algorithm. Such a claim requires a different guarantee. Also, the result uses bounded loss and an i.i.d. sample; replacing these conditions requires a concentration argument appropriate to the new setting.

Wrong reasoning: “The posterior is data-dependent, so its KL divergence from the prior is mutual information.”
Correction: Expected posterior-to-prior divergence also includes $\operatorname{KL}(\overline Q\|P)$. It equals mutual information only when the marginal predictor distribution matches the prior.
Wrong reasoning: “A small expected generalization gap means every selected predictor generalizes well.”
Correction: The theorem bounds an average signed gap. It does not directly bound individual gaps or their tail probabilities.
Wrong reasoning: “Any prior can be chosen after seeing the sample and used in the same calculation.”
Correction: The stated decomposition and prior-based bound use a fixed prior independent of $S$. A data-dependent prior needs a separate argument that accounts for how it was selected.

Key takeaway: For bounded losses, the expected generalization gap of a randomized predictor is controlled by how much information the predictor carries about the sample. Expected posterior-to-prior divergence is an upper bound on that information, but it may additionally charge for a mismatch between the predictor's marginal distribution and the prior.

Check Your Understanding

Answer each question using the definitions and bounds above.

What distribution is used as the independent reference in the definition of $I(S;W)$?
Under what condition does $E_S[\operatorname{KL}(Q_S\|P)]$ equal $I(S;W)$?
For losses in $[0,1]$, how does the mutual-information generalization bound scale with sample size $n$?
Why can a sample-independent algorithm have positive expected posterior-to-prior divergence but zero mutual information?
Does the theorem guarantee that the realized generalization gap is bounded by $\sqrt{I(S;W)/(2n)}$ for every sample? Explain.