PAC-Bayes theory gives high-probability risk bounds for randomized predictors. Its proof is an information inequality plus concentration, not ordinary Bayesian posterior consistency.
Randomized predictors
PAC-Bayes compares a data-dependent distribution over hypotheses with a prior distribution chosen before seeing the sample.
Definition. Let \(\mathcal H\) be a hypothesis space, \(P_0\) a prior probability on \(\mathcal H\), and \(Q\) a data-dependent posterior probability on \(\mathcal H\). The Gibbs risk is \[ R(Q)=\int R(h)\,Q(\mathrm{d}h), \qquad R_n(Q)=\int R_n(h)\,Q(\mathrm{d}h). \]
Remark. The word posterior here means any data-dependent distribution \(Q\). It need not be the Bayesian posterior from a likelihood.
Change of measure
The variational form of KL is the algebraic heart of PAC-Bayes.
Lemma. For any measurable \(\phi\) and any \(Q\ll P_0\), \[ Q\phi\le \operatorname{KL}(Q\|P_0)+\log P_0e^\phi. \]
Proof. By the Donsker-Varadhan variational identity, \[ \log P_0e^\phi=\sup_Q\{Q\phi-\operatorname{KL}(Q\|P_0)\}. \] Rearranging this inequality for the chosen \(Q\) gives the claim. Equivalently, apply Jensen's inequality to \(e^{\phi}/(\mathrm{d}Q/\mathrm{d}P_0)\) under \(Q\).
A basic PAC-Bayes inequality
The bound holds simultaneously over all posteriors because the random quantity integrated over the prior is controlled before choosing \(Q\).
Theorem. Assume \(0\le\ell(h,Z)\le1\). With probability at least \(1-\delta\), for every \(Q\ll P_0\), \[ R(Q)\le R_n(Q)+ \sqrt{\frac{\operatorname{KL}(Q\|P_0)+\log(2\sqrt n/\delta)}{2n}} \] up to standard constants depending on the chosen Bernoulli-kl relaxation.
Proof. For each fixed \(h\), concentration controls the deviation between \(R_n(h)\) and \(R(h)\) in exponential form. Integrate the exponential inequality with respect to \(P_0\) and apply Markov's inequality to obtain a high-probability bound on \(\log P_0e^\phi\). The change-of-measure lemma transfers the result from \(P_0\) to any \(Q\). Finally, relax the Bernoulli-kl form to the displayed square-root form.
Choosing the posterior
PAC-Bayes bounds can be optimized over \(Q\), giving a regularized empirical objective.
Proposition. Minimizing \[ Q R_n+\frac{1}{\eta n}\operatorname{KL}(Q\|P_0) \] over \(Q\) yields the Gibbs distribution \[ Q_\eta(\mathrm{d}h)\propto e^{-\eta nR_n(h)}P_0(\mathrm{d}h). \]
Proof. Use the same variational identity with \(\phi=-\eta nR_n(h)\). The minimizing distribution is the exponentially tilted prior, and the minimum value is \(-(\eta n)^{-1}\log P_0e^{-\eta nR_n}\).
The Donsker-Varadhan identity with equality
Theorem. If \(P_0e^\phi<\infty\), then \[ \log P_0e^\phi =\sup_{Q\ll P_0}\{Q\phi-\operatorname{KL}(Q\|P_0)\}. \] Equality is attained at \[ \frac{\mathrm{d}Q^*}{\mathrm{d}P_0} =\frac{e^\phi}{P_0e^\phi}. \]
Proof. Define \(Q^*\) by the displayed tilt. For arbitrary \(Q\ll P_0\), \[ \operatorname{KL}(Q\|Q^*) =\operatorname{KL}(Q\|P_0)-Q\phi+\log P_0e^\phi\ge0. \] Rearrangement proves the upper bound, and \(Q=Q^*\) makes the KL divergence zero.
A Bernoulli-kl PAC-Bayes theorem
Definition. For \(q,p\in[0,1]\), \[ \operatorname{kl}(q\|p) =q\log\frac qp+(1-q)\log\frac{1-q}{1-p}. \]
Theorem. If losses lie in \([0,1]\), then with probability at least \(1-\delta\), simultaneously for every \(Q\ll P_0\), \[ \operatorname{kl}\{R_n(Q)\|R(Q)\} \le\frac{\operatorname{KL}(Q\|P_0)+\log(2\sqrt n/\delta)}{n}. \]
Proof outline. For each fixed hypothesis \(h\), the binomial method of types gives \[ \mathbb E\exp\{n\operatorname{kl}(R_n(h)\|R(h))\}\le2\sqrt n. \] Integrate over \(P_0\) and apply Markov's inequality. On the resulting event, use the change-of-measure lemma with \(\phi(h)=n\operatorname{kl}(R_n(h)\|R(h))\). Joint convexity of binary KL and Jensen's inequality yield \[ \operatorname{kl}\{QR_n(h)\|QR(h)\} \le Q\operatorname{kl}\{R_n(h)\|R(h)\}. \]
Corollary. Pinsker's inequality gives \[ R(Q)\le R_n(Q)+ \sqrt{\frac{\operatorname{KL}(Q\|P_0)+ \log(2\sqrt n/\delta)}{2n}}. \]
A Catoni bound
Theorem. For every \(\lambda>0\), with probability at least \(1-\delta\), simultaneously for all \(Q\ll P_0\), \[ R(Q)\le \frac{1-\exp\!\left\{-\lambda R_n(Q) -[\operatorname{KL}(Q\|P_0)+\log(1/\delta)]/n\right\}} {1-e^{-\lambda}}. \]
Proof outline. For \(U\in[0,1]\), convexity of \(e^{-\lambda U}\) gives \(\mathbb Ee^{-\lambda U}\le1-(1-e^{-\lambda})\mathbb EU\). Apply this independently to empirical losses, rearrange to an exponential supermartingale involving population risk, integrate under the prior, use Markov, and transfer to \(Q\) by Donsker-Varadhan. Solve the resulting inequality for \(R(Q)\).
Gibbs classifiers and majority votes
Definition. A Gibbs classifier samples \(h\sim Q\) independently for each prediction. Its risk is \(R(Q)\). A majority vote predicts \[ B_Q(x)=\operatorname{sign}\int h(x)\,Q(\mathrm{d}h) \] for \(h(x)\in\{-1,1\}\).
Proposition. \[ R(B_Q)\le2R(Q). \]
Proof. If the majority vote is wrong at \((x,y)\), at least half of the \(Q\)-mass assigns the wrong label. Hence \[ \mathbf1\{B_Q(x)\ne y\} \le2\int\mathbf1\{h(x)\ne y\}\,Q(\mathrm{d}h). \] Integrate over the data law.
The bound can be loose because it ignores dependence among voters. The PAC-Bayes \(C\)-bound additionally uses the first two moments of the vote margin and can exploit low disagreement among accurate voters.
Localized priors and oracle behavior
Proposition. Let \(B(h^*,\varepsilon)\) be a risk-local neighborhood of a comparator \(h^*\), and choose \(Q\) as the prior conditioned on that set. Then \[ \operatorname{KL}(Q\|P_0) =\log\frac1{P_0\{B(h^*,\varepsilon)\}}. \] A PAC-Bayes bound therefore balances local approximation error against logarithmic prior mass, mirroring Bayesian contraction theory.
Proof. The conditional density is \(\mathbf1_B/P_0(B)\). Integrating its log under \(Q\) gives \(\log\{1/P_0(B)\}\).
Data-dependent priors
A prior chosen after inspecting the same sample invalidates the standard proof because the prior can encode the empirical minimizer at no KL cost. Valid alternatives include:
- choose the prior from an independent data split;
- use a hierarchical hyperprior and pay the hyperparameter KL cost;
- prove a differentially private data-dependent-prior theorem;
- construct a distribution-dependent localized prior only inside the analysis, not as a sample-adaptive object.
PAC-Bayes and generalized Bayesian posteriors
Proposition. The Gibbs posterior \[ Q_\eta(\mathrm{d}h)\propto e^{-\eta nR_n(h)}P_0(\mathrm{d}h) \] minimizes the PAC-Bayes objective, but it equals an ordinary Bayesian posterior only when \(\eta nR_n(h)\) is a negative log-likelihood up to an \(h\)-independent constant. Otherwise it is a generalized posterior defined by a loss.
PAC-Bayes bounds are frequentist high-probability statements over the sample, valid for every data-dependent \(Q\) on one event. Bayesian posterior concentration is a statement about a particular likelihood-based random measure under a specified data law. Their variational algebra overlaps, but their inferential meanings remain distinct.