Common Errors in PAC-Bayes Arguments

Why PAC-Bayes Arguments Need Careful Auditing

PAC-Bayes bounds allow a posterior distribution over predictors to depend on the observed sample. This flexibility is useful, but it makes the logic of a proof especially important: the prior must be handled correctly, the divergence must face the right way, and the empirical and population risks must refer to the same posterior. Probability statements also need their quantifiers stated precisely. A derivation can look familiar while failing at any one of these points.

We use the following standard setting. Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $D$. Let $h$ range over a measurable predictor space $\mathcal H$, and suppose the loss $\ell(h,z)$ is measurable and takes values in $[0,1]$. Define

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

for sample $S=(Z_1,\ldots,Z_n)$. For a probability distribution $Q$ on $\mathcal H$, write $R(Q)=E_{h\sim Q}[R(h)]$ and $\widehat R_S(Q)=E_{h\sim Q}[\widehat R_S(h)]$. For $Q$ absolutely continuous with respect to $P$, the Kullback–Leibler divergence is $\operatorname{KL}(Q\|P)=E_Q[\log(dQ/dP)]$; it is $+\infty$ when $Q$ is not absolutely continuous with respect to $P$.

Fixed-prior PAC-Bayes bound: Let $P$ be a probability distribution on $\mathcal H$ fixed independently of $S$. For any fixed $\lambda>0$ and $\delta\in(0,1)$, with probability at least $1-\delta$ over $S$, simultaneously for every $Q\ll P$ with finite $\operatorname{KL}(Q\|P)$, $$ R(Q)\leq \widehat R_S(Q) +\frac{\operatorname{KL}(Q\|P)+\log(1/\delta)}{\lambda} +\frac{\lambda}{8n}. $$ For a $Q$ with infinite divergence, the same inequality is trivially true if its right-hand side is interpreted as $+\infty$.

The Change-of-Measure Step and Its Direction

The algebraic step that turns an exponential average under a prior into a bound for a posterior is a common source of errors. The direction of the divergence is not a convention that can be switched: it follows from integrating with respect to $Q$.

Change-of-measure inequality: Let $P$ and $Q$ be probability distributions with $Q\ll P$ and finite $\operatorname{KL}(Q\|P)$. If $g$ is bounded and measurable, then $$ E_Q[g]\leq \operatorname{KL}(Q\|P)+\log E_P[e^g]. $$

Proof. Put $q=dQ/dP$. Under $Q$, points where $q=0$ have probability zero. Jensen's inequality for the concave logarithm gives

E_Q[g]-\operatorname{KL}(Q\|P) =E_Q\!\left[\log\!\left(\frac{e^g}{q}\right)\right] \leq \log E_Q\!\left[\frac{e^g}{q}\right] =\log\int_{\{q>0\}} e^g\,dP \leq \log E_P[e^g].

The penultimate expression is an integral over $\{q>0\}$, not necessarily the integral over the whole space: if $P(q=0)>0$, that set can omit positive $P$-mass. The inequality is all that is needed. Boundedness of $g$ and finite divergence ensure the expectations used here are well-defined. This proves the claim. $\square$

Notice that the left side is an expectation under $Q$, and the divergence is $\operatorname{KL}(Q\|P)$, not $\operatorname{KL}(P\|Q)$. A proof that changes either distribution without re-deriving the step has not established the stated inequality.

Worked Example: Reversing the Divergence Can Change the Answer

Let the hypothesis space be $\{a,b\}$, with $P(a)=0.9$, $P(b)=0.1$, and $Q(a)=Q(b)=0.5$. Calculate both divergences.

The divergence required by the change-of-measure inequality is

\operatorname{KL}(Q\|P) =0.5\log(0.5/0.9)+0.5\log(0.5/0.1) =0.5\log(25/9) \approx 0.5108.

In the reverse direction,

\operatorname{KL}(P\|Q) =0.9\log(0.9/0.5)+0.1\log(0.1/0.5) =0.9\log(1.8)+0.1\log(0.2) \approx 0.3681.

These are different quantities, so substituting the smaller reverse divergence does not follow from the inequality. The discrepancy can be more serious than a numerical difference: if $P(a)=1$ and $Q(a)=Q(b)=0.5$, then $\operatorname{KL}(P\|Q)=\log 2$ is finite, while $\operatorname{KL}(Q\|P)=+\infty$. The change-of-measure inequality cannot use the finite reverse divergence in place of the required one.

Deriving the Bound and Reading Its Probability Statement

Here is the standard derivation, which also makes clear where the prior-independence condition enters. Fix $P$, $\lambda>0$, and define

g_S(h)=\lambda\bigl(R(h)-\widehat R_S(h)\bigr), \qquad Z(S)=E_{h\sim P}[e^{g_S(h)}].

For a fixed $h$, the random variables $\ell(h,Z_i)$ are independent and lie in $[0,1]$. Hoeffding's lemma states that for a random variable $Y\in[a,b]$, $E[e^{t(Y-EY)}]\leq e^{t^2(b-a)^2/8}$. Applying it to each summand and multiplying the bounds gives

E_S[e^{g_S(h)}] =\prod_{i=1}^n E\!\left[ e^{(\lambda/n)(R(h)-\ell(h,Z_i))} \right] \leq \exp\!\left(\frac{\lambda^2}{8n}\right).

Because the integrand is nonnegative, Tonelli's theorem permits interchanging the expectations over $S$ and $P$. Thus $E_S[Z(S)]\leq e^{\lambda^2/(8n)}$. Markov's inequality implies that, with probability at least $1-\delta$,

Z(S)\leq \frac{e^{\lambda^2/(8n)}}{\delta}.

This is one event determined by $S$ and the fixed $P$. On that event, apply the change-of-measure inequality to $g_S$ for any $Q\ll P$ with finite divergence:

\lambda\bigl(R(Q)-\widehat R_S(Q)\bigr) \leq \operatorname{KL}(Q\|P)+\log Z(S) \leq \operatorname{KL}(Q\|P)+\frac{\lambda^2}{8n}+\log(1/\delta).

Dividing by $\lambda>0$ gives the displayed PAC-Bayes bound. The event did not depend on $Q$, so the result holds simultaneously for all such $Q$. If $Q\ll P$ has infinite divergence, the bound with right-hand side $+\infty$ is trivial; the change-of-measure inequality has not been applied to that case. $\square$

Worked Example: A Sample-Dependent Prior Can Make the Claim False

Let $Z_i$ be independent and uniform on $[0,1]$, and let every observed label be $1$. Use zero-one loss and predictors $h_A(x)=\mathbf{1}\{x\in A\}$, where $A$ ranges over finite subsets of $[0,1]$. For each realized sample, choose $A_S=\{Z_1,\ldots,Z_n\}$, and set both the prior and posterior equal to the point mass at $h_{A_S}$.

With probability one, a uniform draw is not in any fixed finite set, so $R(h_{A_S})=1$: the predictor outputs $0$ on almost every new draw, whose label is $1$. On the observed sample, it outputs $1$ at every observation, so $\widehat R_S(h_{A_S})=0$. Since prior and posterior are the same point mass, $\operatorname{KL}(Q_S\|P_S)=0$.

If one incorrectly inserts this sample-dependent prior into the fixed-prior bound, then for $n=1000$ and $\delta=0.05$ the right-hand side, apart from the empirical risk, is

\frac{\log 20}{\lambda}+\frac{\lambda}{8000}.

Choosing $\lambda=\sqrt{8000\log 20}$, the minimizing value, makes this penalty $2\sqrt{\log(20)/8000}\approx 0.0387$. It would assert that risk $1$ is at most about $0.0387$, with probability at least $0.95$, although the risk is $1$ almost surely. The error is not in the arithmetic: the prior was selected using the evaluation sample, so the fixed-prior argument does not apply.

A prior chosen using data independent of the evaluation sample can instead be treated as fixed after conditioning on that independent data, provided the evaluation sample remains independent with the stated distribution. A data-dependent construction also needs a theorem whose assumptions explicitly justify its use; simply calling a sample-dependent distribution a prior does not do so.

Keep the Risks Matched to the Same Posterior

The bound compares $R(Q)$ with $\widehat R_S(Q)$, where both average risk over the same distribution $Q$. It does not directly compare the population risk averaged under one distribution with empirical risk averaged under another. This remains true when $Q$ depends on $S$: the uniform event permits that choice, but both terms in the inequality still use the chosen $Q$.

Worked Example: Changing the Posterior Changes the Risk

Let $\mathcal H=\{a,b\}$, and suppose the loss of $a$ is always $0$ while the loss of $b$ is always $1$, for every possible observation. Then empirical and population risks agree exactly for each hypothesis. Take $P(a)=0.9$, $P(b)=0.1$, and $Q(a)=0.1$, $Q(b)=0.9$.

The posterior-averaged risks are

R(Q)=0.1(0)+0.9(1)=0.9, \qquad \widehat R_S(Q)=0.1(0)+0.9(1)=0.9.

But averaging empirical risk under $P$ gives $\widehat R_S(P)=0.9(0)+0.1(1)=0.1$, not $0.9$. The valid divergence is $\operatorname{KL}(Q\|P)=0.8\log 9\approx1.758$. A derivation that writes $R(Q)$ on the left and $\widehat R_S(P)$ on the right has substituted a different quantity; the fact that a bound might be numerically loose enough to cover the discrepancy does not make that substitution a consequence of PAC-Bayes.

Fixed-Posterior Guarantees Versus Simultaneous Guarantees

A statement that holds with probability at least $1-\delta$ for each fixed $Q$ is not, by itself, a statement that holds with that probability for every $Q$ at once. The distinction matters because a posterior may be selected after observing the sample. The fixed-prior PAC-Bayes proof above supplies the stronger, simultaneous event: it first bounds $Z(S)$, an event not indexed by $Q$, and then applies the change-of-measure inequality to every admissible $Q$.

Worked Example: Why Pointwise Probability Does Not Give Uniform Probability

Suppose a family has $M=1000$ candidate posteriors, and a proposed argument establishes a failure probability at most $\delta=0.05$ separately for each fixed candidate. The union bound only gives a simultaneous failure probability at most

\sum_{j=1}^{1000}0.05=50,

which yields no useful guarantee after probabilities are capped at $1$. Even if each individual claim is highly reliable, a sample-dependent choice can select a candidate whose individual event failed. A simultaneous PAC-Bayes event avoids this gap. Alternatively, a proof could pay an explicit complexity cost for a finite family, but it cannot silently replace pointwise validity by uniform validity.

Common Mistakes and a Practical Audit

When checking a PAC-Bayes derivation, locate the exact event whose probability is being controlled and check each substitution against its hypotheses. In particular:

Using an evaluation-sample-dependent prior in a fixed-prior theorem. The prior's dependence on the sample changes the argument. Use a result that explicitly permits the construction or ensure the prior is independent of the evaluation sample.
Reversing the divergence. The change-of-measure step derived above produces $\operatorname{KL}(Q\|P)$. The reverse divergence is generally different and may even be finite when the required one is infinite.
Mixing posterior-averaged risks. Check that population risk and empirical risk are both averaged over the same $Q$, with the same loss and sampling distribution.
Dropping “simultaneously” or adding it without proof. A guarantee for each fixed $Q$ does not automatically cover a $Q$ selected from the data. Conversely, a single event obtained before choosing $Q$ can justify data-dependent posterior selection.
Applying a finite-divergence lemma when the divergence is infinite. The standard bound can be read as trivial with an infinite right-hand side, but that case should be separated rather than included in the lemma's hypotheses.

A reliable audit follows the proof's dependencies: identify which quantities are fixed before sampling, verify the direction and finiteness conditions for the divergence, match both risks to the same posterior, and read the probability quantifiers literally. These checks often reveal more than inspecting the final inequality alone.

Check Your Understanding

For each question, identify the proof step or hypothesis that matters.

In the change-of-measure inequality, which divergence appears, and why does integrating under $Q$ determine its direction?
Why can a prior selected from the evaluation sample invalidate the fixed-prior PAC-Bayes argument?
In a valid posterior-averaged risk bound, which distribution must average both population and empirical risk?
What is the difference between a high-probability statement for each fixed $Q$ and one event that holds simultaneously for all $Q$?
How should the fixed-prior bound be interpreted when $\operatorname{KL}(Q\|P)=+\infty$, and why is that not an application of a finite-divergence lemma?