PAC-Bayes and Exponential Weighting

From Empirical Risk to Exponential Weights

Suppose a learner has a collection of predictors and a loss function that measures how well each predictor performs. Empirical risk favors predictors that fit the observed sample, but choosing only the smallest empirical risk can be unstable: a predictor may fit the sample well by chance. A prior distribution provides a reference over predictors, and a KL penalty measures how far a candidate distribution moves from that reference.

Exponential weighting combines these ideas. It assigns more weight to predictors with lower empirical risk, while the prior determines their initial relative weights. The resulting distribution is also a Gibbs posterior: it is the distribution that optimizes a precise trade-off between empirical fit and departure from the prior. A PAC-Bayes inequality then bounds its population risk, even though the posterior itself depends on the data.

Definition: Let \(\mathcal H\) be a measurable predictor space, let \(\pi\) be a probability distribution on \(\mathcal H\) fixed independently of the sample, and let \(\ell(h,z)\in[0,1]\) be a measurable loss. For observations \(Z_1,\ldots,Z_n\), define \(\hat R(h)=n^{-1}\sum_{i=1}^n\ell(h,Z_i)\) and \(R(h)=E[\ell(h,Z)]\), where \(Z\) has the observation distribution. For \(\eta>0\), the Gibbs posterior is \[ \frac{d\rho_\eta}{d\pi}(h) =\frac{\exp\{-\eta n\hat R(h)\}}{Z_\eta}, \qquad Z_\eta=\int_{\mathcal H}\exp\{-\eta n\hat R(h)\}\,\pi(dh). \] For any distribution \(\rho\) on predictors, write \(\hat R(\rho)=\int\hat R(h)\rho(dh)\) and \(R(\rho)=\int R(h)\rho(dh)\).

The factor \(n\) makes \(\eta\) the coefficient in the empirical-risk-plus-complexity objective. Because \(0\leq\hat R(h)\leq1\), the normalizing constant satisfies \(e^{-\eta n}\leq Z_\eta\leq1\), so it is positive and finite. The Gibbs posterior is therefore well defined. In a finite predictor class, each prior weight is simply multiplied by \(\exp\{-\eta n\hat R(h)\}\) and the products are normalized to sum to one.

The Variational Characterization

The Gibbs form is not just a convenient weighting rule. It is exactly the solution to a penalized empirical-risk problem. The penalty is the KL divergence from a candidate distribution to the prior; distributions that put mass where the prior assigns little probability pay more.

Theorem: For every probability distribution \(\rho\) with \(\operatorname{KL}(\rho\|\pi)<\infty\), \[ \hat R(\rho)+\frac{\operatorname{KL}(\rho\|\pi)}{\eta n} = \frac{\operatorname{KL}(\rho\|\rho_\eta)-\log Z_\eta}{\eta n}. \] Consequently, \(\rho_\eta\) minimizes \(\hat R(\rho)+\operatorname{KL}(\rho\|\pi)/(\eta n)\) over such distributions, and the minimum is \(-\log Z_\eta/(\eta n)\). The minimizer is unique up to equality of distributions.

Here \(\operatorname{KL}(\rho\|\pi)=\int\log(d\rho/d\pi)\,d\rho\) when \(\rho\) is absolutely continuous with respect to \(\pi\), and it is infinite otherwise. To prove the identity, use the density defining \(\rho_\eta\). For \(\rho\ll\pi\), its log density relative to \(\pi\) is \(-\eta n\hat R(h)-\log Z_\eta\). Therefore,

\begin{aligned} \operatorname{KL}(\rho\|\rho_\eta) &=\int \log\!\left(\frac{d\rho}{d\pi}(h) \frac{d\pi}{d\rho_\eta}(h)\right)\rho(dh)\\ &=\operatorname{KL}(\rho\|\pi) +\eta n\hat R(\rho)+\log Z_\eta. \end{aligned}

Rearranging gives the claimed identity. KL divergence is nonnegative, with equality exactly when its two distributions agree. The right-hand side is thus minimized at \(\rho=\rho_\eta\), with value \(-\log Z_\eta/(\eta n)\). This proves both the variational characterization and uniqueness. Temperature interpretation: a larger \(\eta\) reduces the coefficient \(1/(\eta n)\) on the KL penalty, so the optimizer can concentrate more strongly on low empirical-risk predictors.

Worked Example: Two Predictors and the Penalized Objective

There are two predictors, \(h_1,h_2\), with prior probabilities \(1/2,1/2\) and empirical risks \(0.2,0.5\). Let \(\eta n=2\). Their unnormalized Gibbs weights are \(e^{-0.4}\) and \(e^{-1}\), so

\rho_\eta(h_1)=\frac{e^{-0.4}}{e^{-0.4}+e^{-1}} =\frac{1}{1+e^{-0.6}}\approx0.6457, \qquad \rho_\eta(h_2)\approx0.3543.

The posterior empirical risk is \(0.2(0.6457)+0.5(0.3543)\approx0.3063\). Its KL divergence from the equal prior is \(0.6457\log(1.2914)+0.3543\log(0.7086)\approx0.0430\). Thus its penalized objective is \(0.3063+0.0430/2\approx0.3278\).

For comparison, placing all mass on \(h_1\) gives objective \(0.2+\log(2)/2\approx0.5466\); placing all mass on \(h_2\) gives \(0.5+\log(2)/2\approx0.8466\). Neither is as good as the Gibbs distribution: it balances empirical performance against the cost of moving away from the prior.

A PAC-Bayes Inequality for Population Risk

The variational result concerns empirical risk. To say something about population risk, we use a high-probability PAC-Bayes-kl inequality. The version below assumes independent observations from a common distribution and a loss in \([0,1]\). Its key feature is that, on one event, it holds for every posterior distribution, including one chosen after seeing the sample.

Theorem (PAC-Bayes-kl inequality): Suppose \(Z_1,\ldots,Z_n\) are independent and identically distributed, the loss is measurable and lies in \([0,1]\), and the prior \(\pi\) is fixed independently of these observations. For any \(0<\delta<1\), with probability at least \(1-\delta\) over the sample, simultaneously for every posterior \(\rho\), \[ \operatorname{kl}\big(\hat R(\rho)\,\|\,R(\rho)\big) \leq \frac{\operatorname{KL}(\rho\|\pi)+\log(2\sqrt n/\delta)}{n}. \] Here \(\operatorname{kl}(q\|p)=q\log(q/p)+(1-q)\log((1-q)/(1-p))\) is the binary KL divergence, with the usual limiting conventions at \(0\) and \(1\).

A useful consequence follows from Pinsker's inequality, which states that \(\operatorname{kl}(q\|p)\geq2(q-p)^2\) for \(q,p\in[0,1]\). Define \(C_\rho=(\operatorname{KL}(\rho\|\pi)+\log(2\sqrt n/\delta))/n\). On the event in the theorem,

2\big(\hat R(\rho)-R(\rho)\big)^2 \leq \operatorname{kl}\big(\hat R(\rho)\|R(\rho)\big) \leq C_\rho, \qquad R(\rho)\leq \hat R(\rho)+\sqrt{C_\rho/2}.

The last inequality follows by taking square roots to get \(\lvert\hat R(\rho)-R(\rho)\rvert\leq\sqrt{C_\rho/2}\), then retaining the upper side of this absolute-value bound. Since a risk cannot exceed one, the upper bound may be sharpened by taking its minimum with one. Applying this consequence to the Gibbs posterior is valid: the PAC-Bayes event holds simultaneously for every \(\rho\), so it includes the data-dependent \(\rho_\eta\).

Population-risk guarantee: Under the assumptions of the PAC-Bayes-kl theorem, with probability at least \(1-\delta\), \[ R(\rho_\eta)\leq \min\left\{1,\, \hat R(\rho_\eta)+ \sqrt{\frac{\operatorname{KL}(\rho_\eta\|\pi)+\log(2\sqrt n/\delta)}{2n}} \right\}. \] The guarantee combines the Gibbs posterior's empirical performance with its actual KL complexity relative to the prior.

Worked Example: Turning a PAC-Bayes Bound Into a Risk Bound

Suppose \(n=100\), \(\delta=0.05\), and a posterior has empirical risk \(0.18\) and KL divergence \(0.4\) from the prior. The PAC-Bayes-kl threshold is

C_\rho=\frac{0.4+\log(2\sqrt{100}/0.05)}{100} =\frac{0.4+\log(200)}{100} \approx\frac{5.6983}{100}=0.05698.

The square-root deviation term is \(\sqrt{0.05698/2}\approx0.1688\). Hence, on the event of probability at least \(0.95\), the posterior population risk is at most \(0.18+0.1688=0.3488\). This is a valid upper bound, though it is not especially sharp. The calculation also shows why a low empirical risk alone is not enough: the sample size and the posterior's KL divergence both affect the guarantee.

Temperature, Fit, and Complexity

The variational theorem gives a precise comparison with any alternative posterior \(\rho\). For every \(\rho\) with finite KL divergence,

\hat R(\rho_\eta)+\frac{\operatorname{KL}(\rho_\eta\|\pi)}{\eta n} \leq \hat R(\rho)+\frac{\operatorname{KL}(\rho\|\pi)}{\eta n}.

This inequality and the population-risk guarantee play different roles. The first says that the Gibbs posterior optimizes an empirical criterion; the second controls its population risk using the posterior's KL divergence. Neither by itself says that the Gibbs posterior has the smallest population risk among all posteriors. The temperature determines the empirical trade-off, while the PAC-Bayes bound quantifies the cost of the posterior's complexity at the chosen confidence level.

Worked Example: How Temperature Changes the Weights

Consider three predictors with prior probabilities \(0.5,0.3,0.2\), empirical risks \(0.1,0.2,0.5\), and \(\eta n=5\). Their unnormalized Gibbs weights are

0.5e^{-0.5}\approx0.3033,\qquad 0.3e^{-1}\approx0.1104,\qquad 0.2e^{-2.5}\approx0.0164.

The normalizing constant is approximately \(0.4300\), giving posterior probabilities approximately \(0.7052,0.2566,0.0382\). The posterior empirical risk is \(0.7052(0.1)+0.2566(0.2)+0.0382(0.5)\approx0.1409\).

At \(\eta n=0\), interpreted as the limit as \(\eta n\) decreases to zero, the weights are the prior probabilities and the mean empirical risk is \(0.5(0.1)+0.3(0.2)+0.2(0.5)=0.21\). The positive temperature has shifted mass toward the better-fitting predictors. It has not discarded the prior: the third predictor retains positive weight, but its risk makes its weight small.

Common Pitfall: Treating the Gibbs Posterior as a Risk Guarantee

A tempting but incorrect argument is: “The Gibbs posterior emphasizes predictors with low empirical risk, so it must have low population risk.” The first part is a description of how the weights are constructed; it is not a generalization theorem. Sampling variability can make empirical risk optimistic, and the amount of optimism that can be certified depends on the sample size and KL divergence.

The correction is to keep the two steps distinct. First, use the variational identity to understand and compare the empirical-risk-plus-KL objective. Then apply a PAC-Bayes inequality under its stated sampling, bounded-loss, and prior-independence assumptions. The resulting high-probability risk bound accounts for the posterior's complexity. If its right-hand side exceeds one, the bound is valid but uninformative; it should not be reported as evidence of a useful guarantee.

Key takeaway: Exponential weighting is the exact minimizer of empirical risk plus a KL penalty relative to a prior. Under independent sampling and bounded loss, a simultaneous PAC-Bayes bound turns the Gibbs posterior's empirical risk and KL divergence into a high-probability upper bound on its population risk.

Check Your Understanding

Use the definitions and inequalities above to answer the following questions.

For a fixed sample, why is the Gibbs posterior well defined when the loss lies in \([0,1]\) and \(\eta\) is finite and positive?
What objective does the Gibbs posterior minimize, and how does increasing \(\eta\) change the coefficient on the KL penalty?
Why can the simultaneous PAC-Bayes-kl event be applied to a posterior selected using the observed sample?
For empirical risk \(q\) and KL threshold \(C\), derive the upper bound \(R(\rho)\leq q+\sqrt{C/2}\) from Pinsker's inequality.
Name two reasons why a small empirical risk may still yield a weak population-risk guarantee.