The PAC-Bayes-KL Inequality

Why Compare Risks in Binary Relative Entropy?

A high-probability PAC-Bayes bound must account for two sources of uncertainty: the data used to estimate risk and the posterior distribution over predictors, which may itself depend on those data. A bound written in binary relative entropy gives a particularly direct comparison between empirical and population Gibbs risk. It also yields an upper confidence limit by solving a one-dimensional inequality.

Throughout, 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 measurable loss. The prior \(\pi\) is a probability distribution on \(\mathcal H\) fixed independently of the sample. A posterior \(\rho\) is any probability distribution on \(\mathcal H\), including one selected after observing the sample.

Write \(\operatorname{KL}(\rho\|\pi)\) for the relative entropy between distributions on predictors. It is finite only when \(\rho\) is absolutely continuous with respect to \(\pi\), with the usual integral definition. The inequality below uses a convenient finite-sample constant \(n+1\). Sharper constants are possible, but the \(n+1\) version follows from a short method-of-types argument.

A Bounded-Loss Exponential-Moment Bound

The first step controls, for a fixed predictor, the exponential of the binary relative entropy between its empirical and population risks. The argument also explains why the result applies to losses anywhere in \([0,1]\), not just zero-one losses.

Proof. First suppose \(0<\mu<1\), and define \(f(x)=\exp\{n\operatorname{kl}(x\|\mu)\}\) on \([0,1]\). Binary relative entropy is convex in its first argument and nonnegative. Since the exponential is convex and increasing, \(f\) is convex. For any random variable \(X\in[0,1]\), convexity gives \(f(X)\le (1-X)f(0)+Xf(1)\). Thus its expected value is no greater than the expected value obtained by replacing \(X\) with a Bernoulli variable having the same mean.

Apply this replacement one coordinate at a time to \(f(n^{-1}\sum_i X_i)\). With all other coordinates fixed, this is a convex function of the remaining coordinate, so each replacement can only increase the expectation. The resulting variables are independent Bernoulli variables with success probability \(\mu\). If \(K\) is their sum, then

At \(k=0\) or \(k=n\), powers with exponent zero are interpreted as one. Each summand simplifies to \({n\choose k}(k/n)^k(1-k/n)^{n-k}\). This is the probability of obtaining exactly \(k\) successes in \(n\) Bernoulli trials with success probability \(k/n\), so it is at most one. There are \(n+1\) summands, proving the bound. If \(\mu=0\) or \(\mu=1\), the variables equal their mean almost surely, and the expectation is one. \(\square\)

The PAC-Bayes-KL Inequality

For a fixed predictor \(h\), apply the lemma to \(X_i=\ell(h,Z_i)\), whose mean is \(R(h)=E_Z[\ell(h,Z)]\). Integrating the resulting exponential bound over the prior gives an event that can be used for every posterior, even a posterior selected using the sample.

Proof. For each sample \(S\), put \(g_S(h)=n\operatorname{kl}(\hat R_S(h)\|R(h))\), where \(\hat R_S(h)=n^{-1}\sum_i\ell(h,Z_i)\). The lemma and integration over \(h\sim\pi\) imply \(E_S E_{h\sim\pi}[\exp\{g_S(h)\}]\le n+1\). Markov’s inequality therefore gives, with probability at least \(1-\delta\), \(E_{h\sim\pi}[\exp\{g_S(h)\}]\le(n+1)/\delta\). Fix any sample in this event.

For any \(\rho\ll\pi\), the change-of-measure inequality gives \(E_\rho[g_S]\le\operatorname{KL}(\rho\|\pi)+\log E_\pi[\exp\{g_S\}]\). This inequality follows by applying Jensen’s inequality to the logarithm under \(\rho\): \(E_\rho[g_S]-\operatorname{KL}(\rho\|\pi) =E_\rho[\log(\exp(g_S)\,d\pi/d\rho)] \le\log E_\pi[\exp(g_S)]\). The displayed expectation is finite on the chosen event.

Finally, binary relative entropy is jointly convex. To see this, use convexity of \(\phi(t)=t\log t\): for nonnegative measurable \(a,b\), \(E[b\phi(a/b)]\ge E[b]\phi(E[a]/E[b])\), with the zero cases understood by continuity. Applying this once to \(a\) and \(b\), and once to \(1-a\) and \(1-b\), proves \(\operatorname{kl}(E_\rho a\|E_\rho b)\le E_\rho[\operatorname{kl}(a\|b)]\). Take \(a=\hat R_S(h)\) and \(b=R(h)\). Combining joint convexity with the change-of-measure inequality and the event bound yields \[ n\operatorname{kl}\bigl(\hat R_S(\rho)\|R(\rho)\bigr) \le E_\rho[g_S] \le\operatorname{KL}(\rho\|\pi)+\log((n+1)/\delta). \] The event did not depend on \(\rho\), so the conclusion holds simultaneously for every posterior. \(\square\)

Turning the Inequality Into an Upper Limit

On the theorem’s event, set \(q=\hat R_S(\rho)\), \(p=R(\rho)\), and \(c=[\operatorname{KL}(\rho\|\pi)+\log((n+1)/\delta)]/n\). The theorem says \(\operatorname{kl}(q\|p)\le c\). For fixed \(q<1\), the function \(u\mapsto\operatorname{kl}(q\|u)\) is increasing for \(u>q\), since its derivative is \((u-q)/(u(1-u))\). Thus the exact upper endpoint is determined by a single binary-entropy equation.

For \(q<1\), the defining root exists and is unique: the function is continuous from zero at \(u=q\), strictly increasing for \(u>q\), and tends to infinity as \(u\) tends to one. The exact root generally has no elementary closed form, but it is readily computed by bisection. A simple algebraic upper limit follows from Pinsker’s inequality for Bernoulli distributions: \(\operatorname{kl}(q\|p)\ge2(q-p)^2\). For completeness, with \(p\) fixed, the second derivative of \(\operatorname{kl}(q\|p)\) in \(q\) is \(1/[q(1-q)]\ge4\). Its value and first derivative at \(q=p\) are zero; integrating the second-derivative bound on either side of \(p\) gives the stated inequality. Consequently,

The root gives the sharper limit; the square-root expression is easier to evaluate and can be more conservative. Both limits inherit the theorem’s probability guarantee and hold for every posterior on the same event.

Interpretation and a Common Pitfall

The complexity term penalizes posteriors that move far from the prior, while the logarithmic confidence term decreases as the requested failure probability increases. The binary relative-entropy form is useful because it respects the bounded risk scale: the inequality is not merely a generic additive deviation statement. Inverting it can give a notably tighter upper limit than the Pinsker-based square-root expression, especially near the endpoints.

• Pitfall: choosing the prior after seeing the sample. The proof begins by bounding the prior-averaged exponential moment over repeated samples. If the prior is selected using the same data without an appropriate correction, that expectation argument does not justify the stated guarantee. The required correction is to use a prior fixed independently of the sample, or to establish a valid procedure for handling data-dependent priors.
• Pitfall: treating a small empirical risk as a population guarantee on its own. The conclusion also depends on sample size, confidence level, and posterior complexity. A data-dependent posterior is allowed, but its divergence from the prior appears explicitly in the bound.
• Pitfall: reversing the inverse. The upper limit is found by increasing the second argument \(u\) of \(\operatorname{kl}(q\|u)\) from \(q\) until the divergence reaches \(c\). It is not obtained by solving for the first argument while holding the population risk fixed.