PAC-Bayes Bounds for Classification Risk

Classification Risk for a Distribution of Predictors

In classification, a learner may return more than one plausible predictor. A posterior distribution over classifiers represents that uncertainty: prediction can draw a classifier from the distribution and use its label. The resulting Gibbs classifier is randomized, even when the posterior has been fixed. A PAC-Bayes bound controls its average zero-one risk, not automatically the risk of every classifier in the posterior or of every deterministic way of combining them.

This distinction matters when a deployed system must make deterministic predictions. In binary classification, the posterior majority vote has a simple risk guarantee derived from Gibbs risk, but that guarantee can be loose. We first define the two risks and establish a PAC-Bayes bound that makes the guarantee for the randomized predictor explicit.

Definition: Let $\mathcal X$ be a feature space, let the label set be $\{-1,+1\}$, and let $\mathcal H$ be a measurable set of classifiers $h:\mathcal X\to\{-1,+1\}$. For a data distribution $D$ on $\mathcal X\times\{-1,+1\}$, define the zero-one loss and the population risk of $h$ by $$ \ell_h(x,y)=\mathbf{1}\{h(x)\ne y\}, \qquad R(h)=E_{(X,Y)\sim D}[\ell_h(X,Y)]. $$ For an independent sample $S=(Z_1,\ldots,Z_n)$, with $Z_i=(X_i,Y_i)\sim D$, define $\widehat R_S(h)=n^{-1}\sum_{i=1}^n\ell_h(X_i,Y_i)$. Given a distribution $\rho$ on $\mathcal H$, the Gibbs population risk and empirical risk are $R(\rho)=E_{h\sim\rho}[R(h)]$ and $\widehat R_S(\rho)=E_{h\sim\rho}[\widehat R_S(h)]$.

The Gibbs risk is the probability of error when a fresh example is drawn from $D$ and a classifier is drawn from $\rho$, independently of that example. A prior $\pi$ is a distribution on $\mathcal H$ fixed independently of the sample; the posterior $\rho$ may depend on $S$. The complexity term is the Kullback–Leibler divergence $ \mathrm{KL}(\rho\|\pi)=E_{h\sim\rho}[\log(d\rho/d\pi)(h)] $ when $\rho$ is absolutely continuous with respect to $\pi$, and is $+\infty$ otherwise.

A PAC-Bayes Bound for Zero-One Risk

The following form gives a valid upper bound with a temperature $\lambda$ chosen in advance. Its event holds simultaneously for every posterior, including posteriors selected after seeing the sample. The fixed-temperature condition is important: optimizing $\lambda$ separately for each data-dependent posterior is not justified by this one-event statement.

Theorem: Suppose $Z_1,\ldots,Z_n$ are independent and identically distributed from $D$, and $\pi$ is a prior independent of the sample. Assume the loss is measurable and takes values in $[0,1]$. For any fixed $\lambda>0$ and $0<\delta<1$, with probability at least $1-\delta$ over $S$, simultaneously for every posterior $\rho$ with finite $\mathrm{KL}(\rho\|\pi)$, $$ R(\rho)\le \widehat R_S(\rho) +\frac{\mathrm{KL}(\rho\|\pi)+\log(1/\delta)}{\lambda} +\frac{\lambda}{8n}. $$

For zero-one loss, the bounded-loss assumption holds automatically. Here is a proof, including the step that makes the guarantee uniform over data-dependent posteriors.

Control an exponential moment.
For fixed $h$, the losses on the independent sample are independent, bounded in $[0,1]$, and have mean $R(h)$. Hoeffding’s lemma gives $E_S[\exp\{\lambda(R(h)-\widehat R_S(h))\}]\le \exp\{\lambda^2/(8n)\}$.

Average over the prior and apply Markov’s inequality.
Integrating the preceding bound with respect to $\pi$ shows that the expectation of $Z_S=\int \exp\{\lambda(R(h)-\widehat R_S(h))\}\,d\pi(h)$ is at most $\exp\{\lambda^2/(8n)\}$. Thus, with probability at least $1-\delta$, $Z_S\le \exp\{\lambda^2/(8n)\}/\delta$.

Change from the prior to any posterior.
On this single event, the variational inequality gives $\lambda E_\rho[R(h)-\widehat R_S(h)]\le \mathrm{KL}(\rho\|\pi)+\log Z_S$ for every $\rho$ of finite divergence. Substitute the bound on $Z_S$ and divide by $\lambda$, obtaining the stated result. The left side is $\lambda(R(\rho)-\widehat R_S(\rho))$, by the definitions of the two posterior risks. $\square$

For completeness, the variational inequality used in the last step follows directly from nonnegativity of KL divergence. For a measurable $g$ with $0<\int e^g\,d\pi<\infty$, define $d\pi_g/d\pi=e^g/\int e^g\,d\pi$. Nonnegativity of $\mathrm{KL}(\rho\|\pi_g)$ implies $E_\rho[g]\le \mathrm{KL}(\rho\|\pi)+\log\int e^g\,d\pi$. In the proof, $g(h)=\lambda(R(h)-\widehat R_S(h))$ is bounded, so its exponential has a finite, positive integral. Measurability of the risks and integrals is assumed as part of the theorem’s setup.

Worked Example: A Posterior Concentrated on One Classifier

Let $\mathcal H=\{h_1,h_2\}$, with prior probabilities $\pi(h_1)=0.9$ and $\pi(h_2)=0.1$. After observing $n=100$ examples, suppose the posterior puts all its mass on $h_2$, whose empirical error rate is $0.08$. Take $\delta=0.05$ and fix $\lambda=20$ before observing the sample.

The divergence is $\mathrm{KL}(\rho\|\pi)=\log(1/0.1)=\log 10\approx2.302585$, since $\rho$ is concentrated on $h_2$. Also, $\log(1/\delta)=\log 20\approx2.995732$. The complexity and confidence contribution is therefore $(2.302585+2.995732)/20\approx0.264916$, and the remaining term is $20/(8\cdot100)=0.025$.

The theorem gives $R(\rho)\le0.08+0.264916+0.025\approx0.369916$. Thus $R(h_2)\le0.370$ is a conservative three-decimal statement on the event of probability at least $0.95$. The guarantee is valid for the selected classifier because the theorem’s event covers every posterior at once.

Worked Example: Averaging Empirical Errors Under a Posterior

Suppose $\mathcal H=\{h_1,h_2\}$, the prior assigns probability $1/2$ to each classifier, and the posterior assigns probabilities $3/4$ and $1/4$. On a sample of size $400$, their empirical error rates are $0.04$ and $0.28$, respectively. Take $\delta=0.05$ and fix $\lambda=50$ in advance.

The posterior empirical risk is $\widehat R_S(\rho)=(3/4)(0.04)+(1/4)(0.28)=0.03+0.07=0.10$. The divergence is $\mathrm{KL}(\rho\|\pi)=(3/4)\log(3/2)+(1/4)\log(1/2)\approx0.130812$. Adding $\log(20)\approx2.995732$ gives $3.126544$. The two penalty terms are $3.126544/50\approx0.062531$ and $50/(8\cdot400)=0.015625$.

Consequently the theorem gives $R(\rho)\le0.10+0.062531+0.015625\approx0.178156$; the conservative rounded upper bound is $0.179$, with confidence at least $0.95$. This is a guarantee for the posterior average of the two classifiers’ risks. It does not assert that each classifier has risk at most $0.179$.

The theorem’s temperature balances two terms: increasing $\lambda$ reduces the divergence-and-confidence contribution but increases $\lambda/(8n)$. The stated probability guarantee applies to the chosen fixed value. If a temperature is selected using the data or a posterior-specific divergence, an additional argument is needed to retain a valid probability statement.

From Gibbs Risk to a Deterministic Vote

For binary classification, define the posterior majority vote $v_\rho$ to predict the label with more posterior mass at $x$; if the masses tie, use a fixed tie-breaking rule. This predictor is deterministic once $\rho$ is fixed. Its risk need not equal $R(\rho)$, because the Gibbs classifier randomizes over classifiers while the vote combines their predictions before scoring.

Proposition: For binary classifiers and any posterior $\rho$, the majority-vote risk satisfies $R(v_\rho)\le 2R(\rho)$.

To prove the claim, fix an example $(x,y)$. Let $q(x,y)=\rho\{h:h(x)\ne y\}$, the posterior mass of classifiers that misclassify this example. If the majority vote is wrong, the posterior mass assigned to the incorrect label is at least the mass assigned to the correct label, including when a tie is broken in favor of the wrong label. Since the two masses sum to one, $q(x,y)\ge1/2$. Therefore, pointwise, $\mathbf{1}\{v_\rho(x)\ne y\}\le2q(x,y)$: if the vote is correct, the left side is zero; if wrong, the right side is at least one. Taking expectation over $(X,Y)\sim D$, and interchanging the nonnegative expectations over examples and $h$, gives $R(v_\rho)\le2E_D[q(X,Y)]=2R(\rho)$. $\square$

Worked Example: A Majority Vote Can Differ from Gibbs Prediction

Let the feature space be $\{a,b\}$, with a deterministic true label $+1$ at both points. Suppose $P(X=a)=0.2$ and $P(X=b)=0.8$. The posterior assigns mass $0.6$ to $h_A$, which predicts $-1$ at $a$ and $+1$ at $b$, and mass $0.4$ to $h_B$, which predicts $+1$ at $a$ and $-1$ at $b$.

At $a$, the posterior error mass is $0.6$; at $b$, it is $0.4$. Hence the Gibbs risk is $R(\rho)=(0.2)(0.6)+(0.8)(0.4)=0.12+0.32=0.44$. The majority vote chooses $h_A$’s label at each point: it is wrong at $a$ and right at $b$. Thus $R(v_\rho)=0.2$, which indeed satisfies $0.2\le2(0.44)=0.88$.

In this example, majority voting improves on the randomized Gibbs predictor. The proposition is an upper bound, not an equality or a promise that voting always improves risk. Applying the PAC-Bayes theorem to $R(\rho)$ and then multiplying its upper bound by two gives a valid, possibly loose, bound for $R(v_\rho)$.

Interpreting the Guarantee

The PAC-Bayes theorem controls the posterior-averaged zero-one risk. If the posterior is data-dependent, the guarantee remains valid because the high-probability event was established before choosing $\rho$ and holds for all such distributions simultaneously. The prior, however, must satisfy the stated independence condition; a prior chosen using the same sample requires a separate justification.

The majority-vote proposition is specific to binary classification. It relies on the fact that if the wrong label wins, at least half of the posterior mass is wrong on that example. That reasoning does not transfer unchanged to multiclass plurality votes: the winning incorrect label may have less than half the total posterior mass. A binary majority-vote guarantee should therefore not be asserted for an arbitrary multiclass vote without another argument.

Common mistake: “A PAC-Bayes bound on the Gibbs risk also bounds the risk of every classifier in the posterior by the same amount.” This is incorrect: an average can be small even when some classifiers have high risk. The bound applies to $E_{h\sim\rho}[R(h)]$; an individual classifier requires its own guarantee, and the binary majority vote is covered here only through the separate factor-two argument.

A second tempting shortcut is to minimize the theorem’s right-hand side over $\lambda$ after seeing the posterior and then report the same confidence level. The theorem above is stated for a fixed $\lambda$, so that direct optimization is not licensed by its event. Temperature selection requires a valid additional procedure or result.

Key takeaway: PAC-Bayes bounds for zero-one classification naturally control the risk of a randomized classifier drawn from the posterior. For binary classification, the deterministic majority vote has risk at most twice the Gibbs risk, but that conversion can be loose and does not say that every posterior member is well-performing.

Check Your Understanding

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

What does $R(\rho)$ average over, and why is it not a guarantee for every $h$ in the support of $\rho$?
Which two conditions on the prior and temperature are needed for the stated PAC-Bayes theorem?
For binary classification, why does a wrong majority vote imply posterior error mass of at least one half on that example?
In the two-point worked example, calculate the Gibbs error mass separately at $a$ and at $b$. Why is the vote’s risk not their posterior average at each point?
Why does the factor-two majority-vote argument not immediately establish the same result for a multiclass plurality vote?

PAC-Bayes Bounds for Classification Risk

What You'll Learn