High-Probability PAC-Bayes Bounds

From Expected Control to a High-Probability Guarantee

An expected PAC-Bayes inequality controls an average over repeated data sets. A high-probability inequality makes a different claim: with probability at least \(1-\delta\) over the sampled data, a risk comparison holds. The central advantage of the PAC-Bayes argument is that this single event can control every posterior distribution at once, including a posterior chosen after seeing the sample.

The construction combines two ingredients. First, bounded losses give exponential concentration for each fixed hypothesis. Averaging those exponential quantities under a prior preserves a bound on their expectation. Markov's inequality then controls that prior average with high probability, and the change-of-measure inequality transfers the control to any posterior.

Setup and Assumptions

Let \(Z_1,\ldots,Z_n\) be independent and identically distributed observations with common distribution \(P\), and write \(S=(Z_1,\ldots,Z_n)\). Let \(\mathcal H\) be a hypothesis space with a probability measure \(\pi\), called the prior. The prior is fixed independently of \(S\). For each \(h\in\mathcal H\), let \(\ell(h,z)\) be its loss on observation \(z\).

The boundedness assumption is what supplies the concentration step below. The iid assumption lets us multiply the single-observation exponential-moment bounds. Measurability ensures that the integrals and events used in the argument are well-defined. A posterior \(Q\) may depend on \(S\); the prior \(\pi\) in this result may not.

The Concentration-and-Change-of-Measure Argument

We first give the exponential concentration bound used in the proof. Hoeffding's lemma states that if a random variable \(Y\) has mean zero and lies in an interval of length \(c\), then, for every real \(t\), $$ E[e^{tY}]\leq e^{t^2c^2/8}. $$ For completeness, normalize a variable in an interval of length \(c\) as \(Y=c(W-p)\), where \(0\leq W\leq1\) and \(p=E[W]\). Convexity of the exponential gives \(e^{sW}\leq (1-W)+We^s\). Taking expectations shows that the moment generating function of \(Y\) is no larger than that of a centered Bernoulli variable with success probability \(p\). The second derivative of the log moment generating function of that centered Bernoulli variable is \(c^2q(1-q)\) for some \(q\in[0,1]\), hence is at most \(c^2/4\). Its log moment generating function and first derivative are both zero at \(t=0\). Integrating the second-derivative bound from zero (in either direction) gives the stated upper bound \(t^2c^2/8\).

To see this, for each \(i\) put \(Y_i=R(h)-\ell(h,Z_i)\). It has mean zero and lies in an interval of length at most one. The observations are independent, so Hoeffding's lemma gives $$ E_S\!\left[e^{\lambda\sum_{i=1}^nY_i}\right] =\prod_{i=1}^n E[e^{\lambda Y_i}] \leq \prod_{i=1}^n e^{\lambda^2/8} =e^{\lambda^2n/8}. $$ The sum in the exponent is \(n(R(h)-\widehat R_S(h))\), as required.

Integrating this result over the prior and using Tonelli's theorem for the nonnegative integrand yields $$ E_S\!\left[\int \exp\!\left\{\lambda n(R(h)-\widehat R_S(h))\right\}\,d\pi(h)\right] \leq e^{\lambda^2n/8}. $$ Markov's inequality therefore bounds this prior average with high probability. The next result transfers that bound from the prior average to every posterior.

The High-Probability PAC-Bayes Bound

Fix \(\lambda>0\) and \(0<\delta<1\). Apply Markov's inequality to the prior exponential average: with probability at least \(1-\delta\) over \(S\), $$ \int \exp\!\left\{\lambda n(R(h)-\widehat R_S(h))\right\}\,d\pi(h) \leq \frac{\exp(\lambda^2n/8)}{\delta}. $$ On this event, apply the change-of-measure inequality with \(g(h)=\lambda n(R(h)-\widehat R_S(h))\). The event depends on the data and prior, but not on \(Q\). Consequently the resulting inequality holds for every posterior on that same event.

Indeed, on the event just established, change of measure gives $$ \lambda n\bigl(R(Q)-\widehat R_S(Q)\bigr) \leq \operatorname{KL}(Q\Vert\pi)+\frac{\lambda^2n}{8}+\log(1/\delta). $$ Dividing by the positive number \(\lambda n\) proves the displayed bound. If the posterior is not absolutely continuous with respect to the prior, or has infinite relative entropy, the bound with an infinite complexity term gives no finite guarantee. \(\square\)

The direction of the deviation matters. Repeating the argument with \(-\lambda n(R(h)-\widehat R_S(h))\) gives a lower-tail bound. Applying each one-sided bound with failure probability \(\delta/2\), and taking the union of their exceptional events, gives the following two-sided version, also simultaneously for every \(Q\), with probability at least \(1-\delta\): $$ \left|R(Q)-\widehat R_S(Q)\right| \leq \frac{\operatorname{KL}(Q\Vert\pi)+\log(2/\delta)}{\lambda n} +\frac{\lambda}{8}. $$ The absolute-value statement uses two applications of Markov's inequality; it does not follow from the one-sided event alone.

Worked Examples

Interpretation and a Common Pitfall

The bound balances three quantities: empirical risk, posterior complexity relative to the prior, and a concentration term. A posterior placing mass on hypotheses that were unlikely under the prior generally pays a larger relative-entropy cost. Increasing \(\lambda\) reduces the complexity contribution but increases \(\lambda/8\); decreasing it has the opposite effect. The result is therefore a family of valid bounds indexed by a fixed positive \(\lambda\), rather than a claim that every choice is equally informative.

Common pitfall: treating a data-chosen tuning parameter as fixed. The theorem guarantees the bound for a fixed \(\lambda\). It does not automatically justify calculating \(\lambda\) from the observed sample and then substituting that value into the same statement: the probability event was proved for the chosen fixed value, not simultaneously for all possible values. The same issue arises if the prior is selected using the sample. To retain a guarantee, the selection procedure needs its own valid argument; simply inserting a data-dependent choice into this theorem is not enough.