PAC-Bayes Guarantees for Approximate Posteriors

Why Posterior Approximation Needs Its Own Error Term

A PAC-Bayes guarantee applies to a distribution over predictors, not only to a single predictor. In practice, the distribution a method can compute may be an approximation to a target posterior: for example, it may come from a numerical procedure or a restricted representation. A guarantee for the target posterior does not automatically become a guarantee for the approximation. The difference in their risks must be controlled, and the PAC-Bayes complexity term may also change.

This tutorial separates these effects. We first give a uniform PAC-Bayes bound for bounded losses, then compare an approximate posterior with a target posterior using total variation. A KL bound can control that discrepancy, but it is important to use the correct direction of KL and not to assume that KL divergence satisfies a triangle inequality.

Setup and a Uniform PAC-Bayes Bound

Let \(\mathcal H\) be a finite hypothesis class, let \(P\) be a prior distribution on \(\mathcal H\) fixed independently of the sample, and let \(Z_1,\ldots,Z_n\) be independent observations from a distribution \(D\). For each \(h\in\mathcal H\), assume the loss \(\ell(h,z)\) is measurable and lies in \([0,1]\). Define the population and empirical risks by

For any 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)]\). The KL divergence is \(\operatorname{KL}(Q\|P)=\sum_h Q(h)\log(Q(h)/P(h))\), with zero-mass terms omitted; it is infinite if \(Q\) assigns positive mass where \(P\) is zero.

The fixed \(\lambda\) matters: the same high-probability event works for every \(Q\), including posteriors chosen after observing the sample. Choosing \(\lambda\) separately from the observed KL of each posterior requires an additional argument. If a family of posteriors is known in advance to satisfy \(\operatorname{KL}(Q\|P)\leq K\), one may choose \(\lambda=\sqrt{8n(K+\log(1/\delta))}\). The resulting bound holds simultaneously over that family, with the two penalty terms summing to \(\sqrt{(K+\log(1/\delta))/(2n)}\).

Proof of the Uniform Bound

For a fixed \(h\), Hoeffding's lemma applied to the independent bounded losses gives

Indeed, \(R(h)-\widehat R_S(h)\) is the average of \(n\) independent centered variables, each with range length at most one; their moment-generating-function bounds multiply. Define \(Z_S=\sum_h P(h)\exp\{\lambda(R(h)-\widehat R_S(h))\}\). Averaging the preceding inequality over \(P\) gives \(E_S[Z_S]\leq \exp(\lambda^2/(8n))\). Markov's inequality therefore implies that, with probability at least \(1-\delta\),

On this event, take any \(Q\) with finite KL divergence. On the support of \(Q\), Jensen's inequality gives the change-of-measure inequality

The first inequality holds because the sum over the support of \(Q\) is only part of the full sum over \(P\); it does not require \(Q\) and \(P\) to have identical supports. Apply this inequality with \(\phi(h)=\lambda(R(h)-\widehat R_S(h))\). Combining it with the bound on \(\log Z_S\), then dividing by \(\lambda\), proves the theorem. The event was defined using \(Z_S\), independently of \(Q\), so the conclusion holds simultaneously for every such \(Q\). \(\square\)

Comparing an Approximate Posterior with Its Target

Let \(\rho\) denote a target posterior and \(Q\) an approximate posterior. Their total variation distance is

For any function \(g:\mathcal H\to[0,1]\), its expectations under these distributions differ by at most this distance. In particular, this holds both for the population risk \(R(h)\) and for the sample-specific empirical risk \(\widehat R_S(h)\).

To see the first inequality, apply the PAC-Bayes theorem to \(\rho\), then use \(R(Q)\leq R(\rho)+\operatorname{TV}(Q,\rho)\). For the second, also use \(\widehat R_S(\rho)\leq\widehat R_S(Q)+\operatorname{TV}(Q,\rho)\). Both applications are permitted even when the posteriors depend on the sample, because the event is uniform over distributions on \(\mathcal H\).

Controlling Risk Discrepancy with KL Divergence

For finite distributions, Pinsker's inequality states that

Here the direction is \(Q\|\rho\): a small \(\operatorname{KL}(Q\|\rho)\) controls the change from the target to the approximation. If \(Q\) puts mass outside the support of \(\rho\), this KL divergence is infinite and gives no such control.

For completeness, let \(A=\{h:Q(h)>\rho(h)\}\). Then \(\operatorname{TV}(Q,\rho)=Q(A)-\rho(A)\). Grouping the terms of the KL sum over \(A\) and its complement gives

This grouping inequality follows by applying Jensen's inequality to the terms in each group; boundary cases follow by continuity or give infinite KL. For fixed \(r\in(0,1)\), the binary expression as a function of \(q\) has value and first derivative zero at \(q=r\), and second derivative \(1/[q(1-q)]\geq4\). Integrating this second-derivative bound between \(r\) and \(q\) yields a lower bound \(2(q-r)^2\). Thus \(\operatorname{KL}(Q\|\rho)\geq2\operatorname{TV}(Q,\rho)^2\), proving the stated inequality.

Substituting Pinsker's inequality into the comparison theorem turns an approximation guarantee in KL into an explicit risk penalty. In the bound using the approximate empirical risk, that penalty is at most \(\sqrt{2\operatorname{KL}(Q\|\rho)}\). Using the target empirical risk instead costs only \(\sqrt{\operatorname{KL}(Q\|\rho)/2}\).

When Approximation Also Changes Complexity

The comparison just proved uses the target's KL complexity and pays explicitly for risk discrepancy. One can instead apply the PAC-Bayes theorem directly to \(Q\), but then the complexity is \(\operatorname{KL}(Q\|P)\). These two complexities cannot generally be interchanged using a triangle inequality: KL is not a metric.

A useful exact identity, when \(Q\ll\rho\ll P\), is

It follows by splitting \(\log(Q/P)=\log(Q/\rho)+\log(\rho/P)\) on the support of \(Q\). If \(\log(\rho(h)/P(h))\leq M\) everywhere that \(Q(h)>0\), then \(\operatorname{KL}(Q\|P)\leq\operatorname{KL}(Q\|\rho)+M\), and this can be substituted into the direct PAC-Bayes bound for \(Q\). Without a condition of this kind, a small KL divergence from \(Q\) to \(\rho\) alone does not ensure that \(Q\)'s prior complexity is close to \(\rho\)'s.

Common Pitfall

A common mistake is to claim that a small \(\operatorname{KL}(Q\|\rho)\) makes the PAC-Bayes bound for \(Q\) nearly identical to the bound for \(\rho\). That conclusion confuses two different quantities: the risk discrepancy, controlled by total variation, and the prior complexity, which is \(\operatorname{KL}(Q\|P)\). The correction is to state which route is being used. Either compare risks and retain the target complexity, or use \(Q\)'s complexity and justify its relationship to the target's. Also, when replacing the target empirical risk with the approximate empirical risk, include the second total-variation term.