PAC-Bayes Generalization Bounds

Intuition Beginner

The earlier bounds in this chapter measured a whole family of rules by one capacity number and asked how badly the family could fool you. PAC-Bayes asks a different, friendlier question. You are allowed to keep not one rule but a whole belief about which rules are good — a way of assigning weight to each rule. You write down a belief before you see any data; call it your prior. Then you look at the data and update to a new belief, your posterior, putting more weight on rules that did well on the sample.

Now imagine flipping a coin against your posterior to pick a rule, and using that randomly chosen rule. PAC-Bayes bounds the average true error of this random pick. The bound says: the average true error is at most the average training error, plus a penalty. And the penalty is paid not for how complicated the rules are, but for how far your posterior strayed from your prior. Stay close to what you believed before the data, and the penalty is small. Move far, and you owe more evidence.

This is a fair trade. Changing your mind a lot in light of data is exactly the move that risks overfitting, so the bound charges you for it, measured by a gap between two beliefs. If your data genuinely support a big change, the lower training error pays for the larger penalty, and the bound still comes out small. That balance is why these bounds can be tight even for huge, flexible models.

Visual Beginner

Picture two clouds of weight over the space of rules. The pale cloud is your prior, spread out before any data. The dark cloud is your posterior, pulled toward the rules that fit the sample. The penalty in the bound is a measure of how much the dark cloud has shifted away from the pale one.

   rules:   r1    r2    r3    r4    r5
   prior:   .     ..    ..    ..    .      (spread, pre-data)
   post:    .     .     ....  ...   .      (pulled toward good fits)
                        ^^^^  ^^^
            penalty grows with how far post moved from prior
   small move  -> small penalty -> bound close to training error
   big move    -> big penalty   -> need much lower training error

How far posterior moved from prior	Penalty	When the bound is still good
barely moved	tiny	training error already low
moderate move	moderate	data strongly favour the shift
huge move	large	only if training error drops a lot

The picture teaches the lesson: you may revise your belief freely, but the bound charges you for the size of the revision, so honest evidence buys cheap revisions and overfitting buys expensive ones.

Worked example Beginner

Take a tiny menu of four rules and suppose your prior puts equal weight $1/4$ on each. After seeing the data you form a posterior that puts weight $1/2$ on the first rule and $1/6$ on each of the other three. We compute the penalty term, which compares posterior to prior.

Step 1. The comparison adds up, over the rules, the posterior weight times the logarithm of (posterior weight divided by prior weight). For rule one: weight $1/2$ times the log of $(1/2)$ divided by $(1/4)$, which is the log of $2$, about $0.693$. So rule one contributes $0.5\times 0.693=0.347$.

Step 2. For each of the other three rules: weight $1/6$ times the log of $(1/6)$ divided by $(1/4)$. The ratio $(1/6)/(1/4)=4/6=0.667$, whose log is about $-0.405$. Each contributes $0.167\times (-0.405)=-0.0676$.

Step 3. Add them: $0.347+3\times (-0.0676)=0.347-0.203=0.144$. This number, about $0.144$, is the divergence of the posterior from the prior — the complexity charge.

Step 4. Suppose the sample has $n=200$ examples and we want $95\%$ confidence, so the confidence amount is the log of $200/0.05$, about $8.29$. The penalty is the square root of $(0.144+8.29)$ divided by $(2\times 199)$, that is the square root of $8.43/398=0.0212$, about $0.146$.

What this tells us: the average true error of a randomly drawn rule is at most its average training error plus about $0.146$. Because the posterior stayed fairly close to the prior, the complexity charge $0.144$ was tiny next to the confidence amount, so the bound is dominated by the sample size, not by how the belief shifted.

Check your understanding Beginner

Formal definition Intermediate+

The setting is the agnostic learning setup of 45.07.05, now with the learner outputting a distribution over hypotheses rather than a single one. Fix a domain $\mathcal{Z}=\mathcal{X}\times \mathcal{Y}$, a distribution $\mathcal{D}$ on $\mathcal{Z}$, a sample $S=(z_1,\dots ,z_n)\sim {\mathcal{D}}^n$, a hypothesis class $\mathcal{H}$, and a loss $\ell :\mathcal{H}\times \mathcal{Z}\to [0,1]$. For $h\in \mathcal{H}$ write the true and empirical risks $L_{\mathcal{D}}(h)={\mathbb{E}}_{z\sim \mathcal{D}}\ell (h,z)$ and $L_S(h)=\frac{1}{n}{\sum }_{i=1}^n\ell (h,z_i)$.

Definition (prior and posterior). A prior is a probability measure $P$ on $\mathcal{H}$ fixed before $S$ is drawn (independent of $S$). A posterior is any probability measure $Q$ on $\mathcal{H}$, permitted to depend on $S$ arbitrarily. The names are borrowed from Bayesian inference, but $Q$ need not be the Bayesian posterior of $P$; it is any data-dependent law ^{[McAllester 1999]}.

Definition (Gibbs / randomised classifier and its risk). The Gibbs classifier associated with $Q$ draws a fresh $h\sim Q$ for each prediction. Its true and empirical risks are the $Q$-averages

$$L_{\mathcal{D}}(Q)={\mathbb{E}}_{h\sim Q}{L}_{\mathcal{D}}(h),L_S(Q)={\mathbb{E}}_{h\sim Q}{L}_S(h).$$

PAC-Bayes bounds $L_{\mathcal{D}}(Q)$ — the average true risk of the randomised classifier — in terms of $L_S(Q)$ and a divergence between $Q$ and $P$.

Definition (KL complexity term). The complexity is the relative entropy (Kullback-Leibler divergence) of 37.07.06,

$$\mathrm{KL}(Q\Vert P)={\mathbb{E}}_{h\sim Q}[\log \frac{dQ}{dP}(h)]={\int }_{\mathcal{H}}\log \frac{dQ}{dP}dQ\in [0,+\infty ],$$

defined to be $+\infty$ when $Q$ is not absolutely continuous with respect to $P$. It replaces the cardinality, VC dimension, or Rademacher complexity of the worst-case theory by a quantity measuring only how far the chosen posterior departs from the prior.

Definition (small-kl). For $p,q\in [0,1]$ the binary relative entropy is $\mathrm{kl}(p\Vert q)=p\log \frac{p}{q}+(1-p)\log \frac{1-p}{1-q}$, the relative entropy of a $\mathrm{Bernoulli}(p)$ against a $\mathrm{Bernoulli}(q)$. Maurer's form of the PAC-Bayes bound is stated in terms of $\mathrm{kl}(L_S(Q)\Vert L_{\mathcal{D}}(Q))$; Pinsker's inequality $\mathrm{kl}(p\Vert q)\ge 2(p-q{)}^2$ of 37.07.06 relaxes it to the square-root form.

Counterexamples to common slips Intermediate+

• "The posterior must be the Bayesian posterior of the prior." It need not be. PAC-Bayes holds for every posterior $Q$ simultaneously, including ones produced by an optimiser, by a heuristic, or by the data-free choice $Q=P$. The freedom to pick $Q$ after the bound is in hand is exactly what makes the bound usable: one optimises $Q$ to minimise the right-hand side.
• "PAC-Bayes bounds the single returned classifier." It bounds the $Q$-averaged risk of the randomised (Gibbs) classifier. Bounding a single deterministic classifier requires a derandomisation step (a margin or majority-vote argument), which costs an extra factor and changes the object being bounded.
• "The prior encodes knowledge of $\mathcal{D}$." The prior must be independent of the sample $S$, but it may encode any data-free belief; a prior chosen with knowledge of $\mathcal{D}$ (not of $S$) is legitimate and yields the sharpest data-distribution-dependent bounds. A prior that peeks at $S$ invalidates the bound, because the change-of-measure step needs ${\mathbb{E}}_S{\mathbb{E}}_{h\sim P}$ to factorise.

Key theorem with proof Intermediate+

The signature result is the McAllester PAC-Bayes bound: the average true risk of the Gibbs classifier exceeds its average empirical risk by no more than a term governed by $\mathrm{KL}(Q\Vert P)$. The proof is a single change of measure — the Donsker-Varadhan variational inequality of 37.07.06 applied to a sub-Gaussian deviation, with the concentration controlled exactly as in 45.07.05 and 40.07.05.

Theorem (McAllester PAC-Bayes bound). Let $P$ be a prior on $\mathcal{H}$ fixed before $S\sim {\mathcal{D}}^n$, and let $\ell$ take values in $[0,1]$. For every $\delta \in (0,1)$, with probability at least $1-\delta$ over $S$, simultaneously for all posteriors $Q$ on $\mathcal{H}$,

$$L_{\mathcal{D}}(Q)\le L_S(Q)+\sqrt{\frac{\mathrm{KL}(Q\Vert P)+\log \frac{n}{\delta }}{2(n-1)}}.$$

^{[McAllester 1999] [Shalev-Shwartz Ben-David 2014]}

Proof. The workhorse is the change-of-measure inequality. For any measurable $f:\mathcal{H}\to \mathbb{R}$ and any $Q$ absolutely continuous with respect to $P$, the Donsker-Varadhan duality of 37.07.06, $\mathrm{KL}(Q\Vert P)={\sup }_g\{{\mathbb{E}}_{h\sim Q}g(h)-\log {\mathbb{E}}_{h\sim P}{e}^{g(h)}\}$, read as a one-sided bound at $g=f$, gives

$${\mathbb{E}}_{h\sim Q}f(h)\le \mathrm{KL}(Q\Vert P)+\log {\mathbb{E}}_{h\sim P}{e}^{f(h)}.\text{\hspace{1em}(∗)}$$

Apply $(\ast )$ with $f(h)=\lambda (n-1)\Delta (h{)}^2$ where $\Delta (h)=L_{\mathcal{D}}(h)-L_S(h)$ and $\lambda >0$ is fixed below. Then for every $Q$,

$$2(n-1){\mathbb{E}}_{h\sim Q}\Delta (h{)}^2\le \frac{2}{\lambda }(\mathrm{KL}(Q\Vert P)+\log {\mathbb{E}}_{h\sim P}{e}^{\lambda (n-1)\Delta (h{)}^2}),$$

after dividing $(\ast )$ by $\lambda /2$. Take the $P$-expectation of the random variable inside the logarithm and bound it. Because $P$ is independent of $S$, Fubini gives ${\mathbb{E}}_S{\mathbb{E}}_{h\sim P}{e}^{\lambda (n-1)\Delta (h{)}^2}={\mathbb{E}}_{h\sim P}{\mathbb{E}}_S{e}^{\lambda (n-1)\Delta (h{)}^2}$. For each fixed $h$, $L_S(h)$ is an average of $n$ independent $[0,1]$ terms with mean $L_{\mathcal{D}}(h)$, so $\Delta (h)$ has a sub-Gaussian moment-generating function; the standard exponential-moment bound for such deviations gives ${\mathbb{E}}_S{e}^{\lambda (n-1)\Delta (h{)}^2}\le \frac{1}{1-2\lambda }\le n$ for the choice $\lambda =\frac{1}{2}(1-1/n)$, uniformly in $h$. Hence ${\mathbb{E}}_S{\mathbb{E}}_{h\sim P}{e}^{\lambda (n-1)\Delta (h{)}^2}\le n$.

Markov's inequality applied to the nonnegative random variable $\xi (S)={\mathbb{E}}_{h\sim P}{e}^{\lambda (n-1)\Delta (h{)}^2}$ gives ${\mathrm{Pr}}_S[\xi (S)\ge n/\delta ]\le \delta$, since ${\mathbb{E}}_S\xi \le n$. So with probability $\ge 1-\delta$, $\log \xi (S)\le \log (n/\delta )$. On this event, for every $Q$ at once,

$$2(n-1){\mathbb{E}}_{h\sim Q}\Delta (h{)}^2\le \frac{2}{\lambda }(\mathrm{KL}(Q\Vert P)+\log \frac{n}{\delta }),$$

and with $\lambda =\frac{1}{2}(1-1/n)$ one has $2/\lambda =4n/(n-1)\le 4$ for the leading constant absorbed below; tracking the constants of the sub-Gaussian step yields the cleaner ${\mathbb{E}}_{h\sim Q}\Delta (h{)}^2\le (\mathrm{KL}(Q\Vert P)+\log (n/\delta ))/(2(n-1))$. Jensen's inequality $({\mathbb{E}}_{h\sim Q}\Delta (h){)}^2\le {\mathbb{E}}_{h\sim Q}\Delta (h{)}^2$ then gives $L_{\mathcal{D}}(Q)-L_S(Q)={\mathbb{E}}_{h\sim Q}\Delta (h)\le \sqrt{{\mathbb{E}}_{h\sim Q}\Delta (h{)}^2}$, which is the stated bound. $\square$

Bridge. This theorem is the foundational reason the data-dependent capacity of 45.07.05 has a Bayesian-flavoured sibling: it shows the uniform deviation is controlled not by a complexity of the whole class but by the divergence $\mathrm{KL}(Q\Vert P)$ of the single chosen posterior from the prior, and the bridge is the Donsker-Varadhan inequality of 37.07.06, which trades a $P$-expectation one can concentrate for the $Q$-expectation one wants to bound at the additive price $\mathrm{KL}(Q\Vert P)$. This is exactly the change-of-measure move that lets a fixed-prior exponential-moment bound become a uniform-over-all-posteriors statement, the same way symmetrisation let the fixed-class bound of 45.07.05 become uniform over hypotheses. It generalises the finite-class union bound, whose $\log |\mathcal{H}|$ term is recovered by taking $P$ uniform and $Q$ a point mass, so $\mathrm{KL}(Q\Vert P)=\log |\mathcal{H}|$. The central insight reappears throughout the chapter: generalisation is the concentration of an exponential moment read against an effective complexity, here the relative entropy. Putting these together, the Hoeffding/sub-Gaussian step is the concentration spine of 40.07.05 supplying the moment bound, and it builds toward the Catoni bound and the optimal Gibbs posterior, where minimising this very right-hand side over $Q$ selects the exponential-weights distribution. The bridge is that $\mathrm{KL}(Q\Vert P)$ is at once a complexity in a learning bound and the rate function of 37.07.06, and it appears again in the free-energy minimisation that closes the chapter.

Exercises Intermediate+

Advanced results Master

The McAllester bound is the entry point to four developments: the sharp binomial-kl form that is tightest at small risk, the Catoni convex-comparison bound with its fast rates, the optimal Gibbs posterior that minimises the bound, and the localisation and data-dependent-prior refinements that make the bounds non-vacuous in practice.

Theorem 1 (Maurer's binomial-kl bound). For a fixed prior $P$ and $\ell \in [0,1]$, with probability $\ge 1-\delta$ over $S\sim {\mathcal{D}}^n$, simultaneously for all $Q$,

$$\mathrm{kl}(L_S(Q)\Vert L_{\mathcal{D}}(Q))\le \frac{\mathrm{KL}(Q\Vert P)+\log \frac{2\sqrt{n}}{\delta }}{n},$$

where $\mathrm{kl}$ is the binary relative entropy ^{[McAllester 1999]}. The proof replaces the squared-deviation potential $f(h)=\lambda (n-1)\Delta (h{)}^2$ by $f(h)=n\mathrm{kl}(L_S(h)\Vert L_{\mathcal{D}}(h))$ in the change-of-measure step, using Maurer's exact lemma ${\mathbb{E}}_S{e}^{n\mathrm{kl}(L_S(h)\Vert L_{\mathcal{D}}(h))}\le 2\sqrt{n}$ in place of the Hoeffding sub-Gaussian bound. Inverting the binary-kl recovers the McAllester square-root bound through Pinsker, $\mathrm{kl}(p\Vert q)\ge 2(p-q{)}^2$ of 37.07.06, but is strictly tighter when $L_S(Q)$ is near $0$ or $1$, where the binomial confidence interval is asymmetric — the regime of interpolating, low-empirical-risk learners.

Theorem 2 (Catoni's bound and fast rates). Fix $\beta >0$. With probability $\ge 1-\delta$, for all $Q$,

$$L_{\mathcal{D}}(Q)\le \frac{1-e^{-\beta L_S(Q)-\frac{1}{n}(\mathrm{KL}(Q\Vert P)+\log \frac{1}{\delta })}}{1-e^{-\beta }},$$

a convex comparison through the function ${\Phi }_{\beta }(p)=\frac{1-e^{-\beta p}}{1-e^{-\beta }}$ ^{[Catoni 2007]}. For small $\beta$ this reduces to McAllester's bound; for the optimal $\beta \asymp \sqrt{n}$ and under a Bernstein/Mammen-Tsybakov low-noise condition relating $L_{\mathcal{D}}(h)-L_{\mathcal{D}}(h^{\star })$ to its variance, the bound yields a fast $O((\mathrm{KL}+\log (1/\delta ))/n)$ rate rather than the worst-case $O(\sqrt{(\mathrm{KL}+\log (1/\delta ))/n})$. The temperature $\beta$ is the same inverse temperature that parametrises the Gibbs posterior; Catoni's monograph reads the entire PAC-Bayes theory as the thermodynamics of the free energy $-\frac{1}{\beta }\log {\mathbb{E}}_P{e}^{-\beta n{L}_S}$, with $\mathrm{KL}(Q\Vert P)$ the entropy and $L_S(Q)$ the energy.

Theorem 3 (the optimal Gibbs posterior). For fixed $\beta$, the posterior minimising the Catoni/McAllester right-hand side over all $Q\ll P$ is the Gibbs posterior $d{Q}_{\beta }^{\star }(h)\propto e^{-\beta n{L}_S(h)}dP(h)$, the unique minimiser of the free-energy functional $\beta n{L}_S(Q)+\mathrm{KL}(Q\Vert P)$ ^{[Catoni 2007]}. This is the Gibbs variational principle of 37.07.06 applied to the empirical-risk potential, and it is precisely the exponential-weights / multiplicative-weights distribution: $Q_{\beta }^{\star }$ is the continuous-domain analogue of the exponentiated-gradient iterate, and the free-energy minimisation is mirror descent with the negative-entropy mirror map. As $\beta \to 0$, $Q_{\beta }^{\star }\to P$ (no data influence); as $\beta \to \infty$, $Q_{\beta }^{\star }$ concentrates on the empirical risk minimisers. The plug-in PAC-Bayes bound at $Q_{\beta }^{\star }$ is the tightest achievable for that $\beta$, and optimising $\beta$ as well balances energy against entropy.

Theorem 4 (data-dependent priors and non-vacuous bounds). The prior must be independent of $S$, but it may depend on $\mathcal{D}$, or be learned from a held-out split of the data; choosing $P$ close to the region where $Q$ will land shrinks $\mathrm{KL}(Q\Vert P)$ and tightens the bound ^{[Catoni 2007]}. For stochastic neural networks, optimising a Gaussian posterior $Q=\mathcal{N}(\mu ,\Sigma )$ against a Gaussian prior to directly minimise the PAC-Bayes right-hand side produces numerically non-vacuous generalization certificates — bounds strictly below the worst-case value $1$ — even for over-parametrised networks, because $\mathrm{KL}(Q\Vert P)$ measures a norm-like distance in weight space rather than the parameter count ^{[McAllester 1999]}. This is the route by which PAC-Bayes, alone among the classical bounds of this chapter, gives non-vacuous numbers for deep networks: the complexity is the description length of the learned weights under the prior code, not the dimension of the weight space.

Synthesis. The foundational reason PAC-Bayes exists as a separate pillar is that one quantity — the relative entropy $\mathrm{KL}(Q\Vert P)$ of the chosen posterior from the prior — governs the generalisation gap, the optimal posterior, and, through temperature, the rate, and every result here is that single quantity read through a different operation. This is exactly the meeting of the change-of-measure inequality of 37.07.06 and the concentration of 40.07.05 that also powered 45.07.05: Donsker-Varadhan produces the $\mathrm{KL}$ term, Hoeffding (or Maurer) bounds the prior-averaged exponential moment, and putting these together the worst-case capacity of the distribution-free theory becomes the posterior-adapted $\mathrm{KL}(Q\Vert P)$, which recovers the finite-class $\log |\mathcal{H}|$ bound through a point-mass posterior as its special case and improves on it whenever the posterior stays near a well-chosen prior.

The Maurer and Catoni bounds are dual readings of the same change of measure — squared deviation versus binary-kl versus convex ${\Phi }_{\beta }$ — and the Gibbs posterior is the central insight that links the bound to optimisation: minimising the PAC-Bayes right-hand side is the free-energy minimisation of 37.07.06, which is exactly mirror descent with the entropic mirror map, so the optimal learner and the optimal certificate are one object. The bridge upward at every level is the same: the cardinality $|\mathcal{H}|$ generalises to $\mathrm{KL}(Q\Vert P)$, the union bound generalises to the change of measure, and the high-probability upgrade is always Markov on a prior-averaged exponential moment whose concentration is the spine of 40.07.05; PAC-Bayes is therefore the Occam/MDL principle made quantitative, with $\mathrm{KL}(Q\Vert P)$ the code length that a shorter description of the data buys back.

Full proof set Master

Proposition 1 (change-of-measure / Donsker-Varadhan inequality). Let $P,Q$ be probability measures on $\mathcal{H}$ with $Q\ll P$, and $f:\mathcal{H}\to \mathbb{R}$ measurable with ${\mathbb{E}}_{h\sim P}{e}^{f(h)}<\infty$. Then ${\mathbb{E}}_{h\sim Q}f(h)\le \mathrm{KL}(Q\Vert P)+\log {\mathbb{E}}_{h\sim P}{e}^{f(h)}$, with equality iff $dQ/dP\propto e^f$.

Proof. Let $\rho =dQ/dP$ and let $Q_f$ be the tilted measure $d{Q}_f=e^{f}dP/Z$ with $Z={\mathbb{E}}_P{e}^f$. Then

$$\mathrm{KL}(Q\Vert P)-{\mathbb{E}}_{Q}f={\mathbb{E}}_Q\log \rho -{\mathbb{E}}_{Q}f={\mathbb{E}}_Q\log \frac{\rho }{e^f}={\mathbb{E}}_Q\log \frac{\rho }{e^f/Z}-\log Z=\mathrm{KL}(Q\Vert Q_f)-\log Z.$$

Since $\mathrm{KL}(Q\Vert Q_f)\ge 0$ by Gibbs' inequality of 37.07.06, $\mathrm{KL}(Q\Vert P)-{\mathbb{E}}_{Q}f\ge -\log Z=-\log {\mathbb{E}}_P{e}^f$, which rearranges to the claim, with equality iff $\mathrm{KL}(Q\Vert Q_f)=0$, i.e. $Q=Q_f$, i.e. $dQ/dP\propto e^f$. $\square$

Proposition 2 (prior-averaged exponential moment). Fix a prior $P$ independent of $S\sim {\mathcal{D}}^n$ and $\ell \in [0,1]$. With $\Delta (h)=L_{\mathcal{D}}(h)-L_S(h)$, ${\mathbb{E}}_S{\mathbb{E}}_{h\sim P}{e}^{2(n-1)\Delta (h{)}^2}\le n$.

Proof. By Fubini (the integrand is nonnegative and $P\perp S$), ${\mathbb{E}}_S{\mathbb{E}}_{h\sim P}{e}^{2(n-1)\Delta (h{)}^2}={\mathbb{E}}_{h\sim P}{\mathbb{E}}_S{e}^{2(n-1)\Delta (h{)}^2}$. Fix $h$. By Pinsker's inequality of 37.07.06, $\mathrm{kl}(L_S(h)\Vert L_{\mathcal{D}}(h))\ge 2\Delta (h{)}^2$, so $e^{2(n-1)\Delta (h{)}^2}\le e^{(n-1)\mathrm{kl}(L_S(h)\Vert L_{\mathcal{D}}(h))}$. Maurer's lemma states that for $n{L}_S(h)$ a sum of $n$ independent $[0,1]$ variables with mean $n{L}_{\mathcal{D}}(h)$, ${\mathbb{E}}_S{e}^{(n-1)\mathrm{kl}(L_S(h)\Vert L_{\mathcal{D}}(h))}\le n$ (the binomial case being extremal). Hence ${\mathbb{E}}_S{e}^{2(n-1)\Delta (h{)}^2}\le n$ for every $h$, and averaging over $h\sim P$ preserves the bound. $\square$

Proposition 3 (McAllester PAC-Bayes bound). With $P,\ell$ as above and $\delta \in (0,1)$, with probability $\ge 1-\delta$ over $S$, for all $Q\ll P$, $L_{\mathcal{D}}(Q)\le L_S(Q)+\sqrt{(\mathrm{KL}(Q\Vert P)+\log (n/\delta ))/(2(n-1))}$.

Proof. Let $\xi (S)={\mathbb{E}}_{h\sim P}{e}^{2(n-1)\Delta (h{)}^2}$. By Proposition 2, ${\mathbb{E}}_S\xi \le n$, so Markov gives ${\mathrm{Pr}}_S[\xi (S)\ge n/\delta ]\le \delta$. Condition on the event $\xi (S)<n/\delta$, of probability $\ge 1-\delta$. Apply Proposition 1 with $f(h)=2(n-1)\Delta (h{)}^2$: for every $Q$,

$${\mathbb{E}}_{h\sim Q}2(n-1)\Delta (h{)}^2\le \mathrm{KL}(Q\Vert P)+\log \xi (S)<\mathrm{KL}(Q\Vert P)+\log (n/\delta ).$$

Dividing by $2(n-1)$, ${\mathbb{E}}_{h\sim Q}\Delta (h{)}^2<(\mathrm{KL}(Q\Vert P)+\log (n/\delta ))/(2(n-1))$. By Jensen, $(L_{\mathcal{D}}(Q)-L_S(Q){)}^2=({\mathbb{E}}_Q\Delta {)}^2\le {\mathbb{E}}_Q{\Delta }^2$, and the deviation $L_{\mathcal{D}}(Q)-L_S(Q)$ is bounded above by its absolute value, so taking square roots gives the claim. The bound is uniform in $Q$ because Proposition 1 and the event $\{\xi (S)<n/\delta \}$ hold for all $Q$ at once. $\square$

Proposition 4 (Gibbs posterior minimises the free energy). Fix $\beta >0$ and define $F(Q)=\beta n{L}_S(Q)+\mathrm{KL}(Q\Vert P)$. Then ${\min }_{Q\ll P}F(Q)=-\log {\mathbb{E}}_{h\sim P}{e}^{-\beta n{L}_S(h)}$, attained uniquely at $d{Q}_{\beta }^{\star }(h)\propto e^{-\beta n{L}_S(h)}dP(h)$.

Proof. Apply Proposition 1's equality case with $f(h)=-\beta n{L}_S(h)$: for every $Q$, ${\mathbb{E}}_{Q}f\le \mathrm{KL}(Q\Vert P)+\log {\mathbb{E}}_P{e}^f$, i.e. $-\beta n{L}_S(Q)\le \mathrm{KL}(Q\Vert P)+\log {\mathbb{E}}_P{e}^{-\beta n{L}_S}$, i.e. $F(Q)\ge -\log {\mathbb{E}}_P{e}^{-\beta n{L}_S}$, with equality iff $dQ/dP\propto e^{-\beta n{L}_S}$. The tilted measure $Q_{\beta }^{\star }$ achieves equality, and uniqueness follows from the strict positivity of $\mathrm{KL}(Q\Vert Q_{\beta }^{\star })$ for $Q\ne Q_{\beta }^{\star }$, as in Proposition 1. $\square$

Proposition 5 (majority-vote derandomisation). For binary $\mathcal{H}$ under $0$–$1$ loss and $g_Q(x)=\mathrm{sign}{\mathbb{E}}_{h\sim Q}h(x)$, $L_{\mathcal{D}}(g_Q)\le 2L_{\mathcal{D}}(Q)$.

Proof. For any $(x,y)$, if $g_Q(x)\ne y$ then the weighted vote favoured the wrong label, so ${\mathbb{E}}_{h\sim Q}1[h(x)\ne y]\ge \frac{1}{2}$; thus $1[g_Q(x)\ne y]\le 2{\mathbb{E}}_{h\sim Q}1[h(x)\ne y]$ pointwise (the inequality is automatic when $g_Q(x)=y$, the left side being $0$). Taking ${\mathbb{E}}_{(x,y)\sim \mathcal{D}}$ and applying Fubini to exchange the $\mathcal{D}$- and $Q$-expectations gives $L_{\mathcal{D}}(g_Q)\le 2{\mathbb{E}}_{h\sim Q}{L}_{\mathcal{D}}(h)=2L_{\mathcal{D}}(Q)$. $\square$

Connections Master

This unit closes the statistical-learning-theory chapter alongside the data-dependent bounds of 45.07.05. Where Rademacher complexity measures the capacity of the whole loss class through its average alignment with random signs, PAC-Bayes measures only the divergence $\mathrm{KL}(Q\Vert P)$ of a single chosen posterior from a fixed prior; the two are complementary readings of the same generalisation problem, and the finite-class $\log |\mathcal{H}|$ bound that Massart's lemma delivers in 45.07.05 is recovered here by a point-mass posterior against a uniform prior, exhibiting both as refinements of the union bound of 45.07.04.

The proof engine is the Donsker-Varadhan variational formula and the Gibbs variational principle of 37.07.06: the change-of-measure inequality ${\mathbb{E}}_{Q}f\le \mathrm{KL}(Q\Vert P)+\log {\mathbb{E}}_P{e}^f$ is exactly the one-sided reading of that unit's duality, and the optimal Gibbs posterior $d{Q}_{\beta }^{\star }\propto e^{-\beta n{L}_S}dP$ is its tilted-measure maximiser specialised to the empirical-risk potential. The relative entropy that is a large-deviations rate function in 37.07.06 is the learning-theoretic complexity here.

The high-probability upgrade rests on the concentration spine of 40.07.05: the prior-averaged exponential moment ${\mathbb{E}}_S{\mathbb{E}}_P{e}^{2(n-1){\Delta }^2}$ is controlled by the Hoeffding/Maurer sub-Gaussian bound established there, the same per-hypothesis exponential-moment tool that fed the McDiarmid step of 45.07.05, with Markov's inequality replacing the union bound. The bounded-differences machinery of 40.07.05 is what makes the single-sample PAC-Bayes certificate computable.

The Gibbs/exponential-weights posterior links PAC-Bayes to optimisation: minimising the bound is a free-energy minimisation that coincides with mirror descent under the negative-entropy mirror map, the continuous-domain analogue of the multiplicative-weights and exponentiated-gradient updates of 44.06.05, so the optimal certificate and the optimal stochastic learner are the same object — the thermodynamic reading Catoni develops, and the formal bridge from generalisation theory to the convex-optimisation chapter.

Historical & philosophical context Master

The PAC-Bayesian theorem was introduced by David McAllester in 1999, first at the Conference on Computational Learning Theory and then in Machine Learning, giving the bound on the Gibbs classifier's risk in terms of the relative entropy between a data-dependent posterior and a data-free prior, and identifying the bound's uniformity over all posteriors as the feature that lets the posterior be optimised after the fact ^{[McAllester 1999]}. The framework synthesised the PAC tradition of Valiant and Vapnik-Chervonenkis with the Bayesian and minimum-description-length ideas of Rissanen and the model-averaging bounds of Shawe-Taylor and Williamson, recasting Occam's razor as the quantitative statement that the complexity charge is the code length $\mathrm{KL}(Q\Vert P)$ of the posterior under the prior code.

The convex-analytic and thermodynamic development is due to Olivier Catoni, whose 2007 IMS monograph established the tightest constants, the convex-comparison bound, the localisation technique, and the reading of the whole theory as the thermodynamics of statistical learning, with the Gibbs posterior $d{Q}_{\beta }^{\star }\propto e^{-\beta n{L}_S}dP$ as the free-energy minimiser and $\beta$ an inverse temperature ^{[Catoni 2007]}. The sharp binomial-kl form and its clean proof through an exact exponential-moment lemma are due to Andreas Maurer (2004). The assembly of the framework into a textbook theorem with the Donsker-Varadhan change-of-measure proof, the form bounding the Gibbs classifier through $\mathrm{KL}(Q\Vert P)$, is the treatment of Shalev-Shwartz and Ben-David (2014) ^{[Shalev-Shwartz Ben-David 2014]}. The framework returned to prominence when Dziugaite and Roy (2017) used it to compute the first non-vacuous generalization bounds for stochastic deep neural networks by directly optimising the posterior.

Bibliography Master

@inproceedings{mcallester1999colt,
  author    = {McAllester, David A.},
  title     = {{PAC}-{Bayesian} model averaging},
  booktitle = {Proceedings of the Twelfth Annual Conference on Computational Learning Theory (COLT)},
  pages     = {164--170},
  year      = {1999}
}

@article{mcallester1999ml,
  author  = {McAllester, David A.},
  title   = {Some {PAC}-{Bayesian} theorems},
  journal = {Machine Learning},
  volume  = {37},
  number  = {3},
  pages   = {355--363},
  year    = {1999}
}

@book{catoni2007,
  author    = {Catoni, Olivier},
  title     = {{PAC}-{Bayesian} Supervised Classification: The Thermodynamics of Statistical Learning},
  series    = {IMS Lecture Notes - Monograph Series},
  volume    = {56},
  publisher = {Institute of Mathematical Statistics},
  year      = {2007}
}

@inproceedings{maurer2004,
  author    = {Maurer, Andreas},
  title     = {A note on the {PAC} {Bayesian} theorem},
  booktitle = {arXiv:cs/0411099},
  year      = {2004}
}

@book{shalevshwartzbendavid2014,
  author    = {Shalev-Shwartz, Shai and Ben-David, Shai},
  title     = {Understanding Machine Learning: From Theory to Algorithms},
  publisher = {Cambridge University Press},
  year      = {2014}
}

@inproceedings{dziugaiteroy2017,
  author    = {Dziugaite, Gintare Karolina and Roy, Daniel M.},
  title     = {Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data},
  booktitle = {Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence (UAI)},
  year      = {2017}
}

@article{germain2016,
  author  = {Germain, Pascal and Bach, Francis and Lacoste, Alexandre and Lacoste-Julien, Simon},
  title   = {{PAC}-{Bayesian} theory meets {Bayesian} inference},
  journal = {Advances in Neural Information Processing Systems},
  volume  = {29},
  year    = {2016}
}