Catoni's Variational PAC-Bayes Bound

Why Catoni’s Bound Has an Exponential Transform

A PAC-Bayes guarantee must account for two sources of difficulty: how well a posterior distribution performs on the observed sample, and how far that posterior departs from a prior chosen independently of the sample. Catoni’s bound combines these quantities, but it does not simply add a complexity penalty to empirical risk. Instead, it places their sum inside an increasing exponential transform of the risk.

The bounded-loss assumption is what makes this transform possible. A chord bound for the exponential function controls the moment of each loss; independence then turns the one-observation control into a product over the sample. The resulting probability statement holds simultaneously for every posterior, including one selected after seeing the data.

Definition: Let \(Z_1,\ldots,Z_n\) be independent and identically distributed observations from a distribution \(P\). Let \(\mathcal H\) be a measurable hypothesis space, let \(\pi\) be a probability distribution on \(\mathcal H\) fixed independently of the sample, and let \(\ell:\mathcal H\times\mathcal Z\to[0,1]\) be a measurable loss. For \(h\in\mathcal H\), define its true risk and empirical risk by

R(h)=E[\ell(h,Z)],\qquad \widehat R(h)=\frac{1}{n}\sum_{i=1}^n\ell(h,Z_i).

For a probability distribution \(\rho\) on \(\mathcal H\), write \(E_\rho R= \int R(h)\,\rho(dh)\) and \(E_\rho\widehat R=\int \widehat R(h)\,\rho(dh)\). Its Kullback–Leibler divergence from \(\pi\) is \(\operatorname{KL}(\rho\Vert\pi)=\int \log(d\rho/d\pi)\,d\rho\) when \(\rho\) is absolutely continuous with respect to \(\pi\), and is \(+\infty\) otherwise.

The Exponential-Moment Bound

Fix a temperature parameter \(\lambda>0\), and put \(c_\lambda=1-e^{-\lambda}\), so \(0<c_\lambda<1\). For a single loss value \(x\in[0,1]\), convexity of \(x\mapsto e^{-\lambda x}\) implies that its value lies below the chord joining its values at 0 and 1:

e^{-\lambda x}\leq (1-x)e^0+xe^{-\lambda} =1-c_\lambda x.

Taking expectation for a fixed hypothesis gives \(E[e^{-\lambda\ell(h,Z)}]\leq 1-c_\lambda R(h)\). Since the observations are independent, the exponential moment of the empirical sum factors into \(n\) one-observation moments. This gives the key bound below.

Lemma: Under the assumptions in the definition, for every fixed \(h\in\mathcal H\) and every \(\lambda>0\),

E\left[ \frac{\exp\{-\lambda n\widehat R(h)\}} {\{1-c_\lambda R(h)\}^{n}} \right]\leq 1.

Proof. The numerator is \(\exp\{-\lambda\sum_{i=1}^n\ell(h,Z_i)\}\). Independence and the chord inequality give

E\left[\exp\left\{-\lambda\sum_{i=1}^n\ell(h,Z_i)\right\}\right] =\prod_{i=1}^n E[e^{-\lambda\ell(h,Z_i)}] \leq \{1-c_\lambda R(h)\}^n.

The denominator is positive and does not depend on the sample. Dividing by it proves the assertion. \(\square\)

Integrate the lemma with respect to \(\pi\). Because the integrand is nonnegative, Tonelli’s theorem permits exchanging the expectation over the sample and the integral over hypotheses. Thus the expectation of the integrated quantity is at most one. Markov’s inequality then says that, with probability at least \(1-\delta\) over the sample,

\int_{\mathcal H} \frac{\exp\{-\lambda n\widehat R(h)\}} {\{1-c_\lambda R(h)\}^{n}}\,\pi(dh) \leq \frac{1}{\delta}.

This event concerns the prior integral and does not depend on a choice of posterior. That fact is what will allow a single event to support a guarantee for all posteriors at once.

Catoni’s Variational PAC-Bayes Bound

The change-of-measure inequality says that, for a measurable function \(g\) and any \(\rho\) absolutely continuous with respect to \(\pi\),

E_\rho[g]\leq \operatorname{KL}(\rho\Vert\pi) +\log E_\pi[e^g],

whenever the terms are well defined. Apply it on the high-probability event above to \(g(h)=-\lambda n\widehat R(h)-n\log\{1-c_\lambda R(h)\}\). The logarithm of \(e^g\) is exactly the logarithm of the integrand in that event. Rearranging and using the convexity of \(-\log(1-c_\lambda r)\) gives the risk guarantee.

Theorem (Catoni’s variational PAC-Bayes bound): Under the assumptions in the definition, for any fixed \(\lambda>0\) and \(0<\delta<1\), with probability at least \(1-\delta\) over the sample, simultaneously for every posterior \(\rho\) with finite \(\operatorname{KL}(\rho\Vert\pi)\),

E_\rho R \leq \frac{ 1-\exp\left\{-\lambda E_\rho\widehat R -\dfrac{\operatorname{KL}(\rho\Vert\pi)+\log(1/\delta)}{n}\right\} }{1-e^{-\lambda}}.

Proof. Work on the event where the prior integral is at most \(1/\delta\). Applying the change-of-measure inequality to the stated \(g\) yields

-\lambda n E_\rho\widehat R -n E_\rho\log\{1-c_\lambda R\} \leq \operatorname{KL}(\rho\Vert\pi)+\log(1/\delta).

Define \(\phi(r)=-\log(1-c_\lambda r)\) for \(r\in[0,1]\). Its second derivative is \(c_\lambda^2/(1-c_\lambda r)^2>0\), so \(\phi\) is convex. The last display therefore implies

\phi(E_\rho R) \leq E_\rho\phi(R) \leq \lambda E_\rho\widehat R+ \frac{\operatorname{KL}(\rho\Vert\pi)+\log(1/\delta)}{n}.

Since \(\phi\) is increasing, exponentiating the inequality \(-\log(1-c_\lambda E_\rho R)\leq A\), where \(A=\lambda E_\rho\widehat R+(\operatorname{KL}(\rho\Vert\pi)+\log(1/\delta))/n\), gives \(1-c_\lambda E_\rho R\geq e^{-A}\). Rearrangement yields the theorem’s bound. The high-probability event was selected before choosing \(\rho\), so the conclusion holds simultaneously for all such posteriors. \(\square\)

The theorem is a variational guarantee in the sense that it applies to every posterior and makes the relevant trade-off explicit. For fixed \(\lambda\), a smaller posterior empirical risk improves the bound, while a posterior farther from the prior incurs a larger KL penalty. The function of these two quantities on the right-hand side is increasing, so any posterior with a smaller value of \(\lambda E_\rho\widehat R+\operatorname{KL}(\rho\Vert\pi)/n\) has at least as favorable a guarantee.

Worked Applications

Worked Example: A Posterior with a KL Penalty of \(\log 2\)

Suppose \(n=50\), \(\lambda=0.5\), \(\delta=0.1\), and a posterior has empirical risk \(E_\rho\widehat R=0.10\) and \(\operatorname{KL}(\rho\Vert\pi)=\log 2\). Compute its Catoni risk bound.

The exponent’s positive quantity is

A=0.5(0.10)+\frac{\log 2+\log 10}{50} =0.05+\frac{0.693147+2.302585}{50} \approx 0.109915.

The denominator is \(1-e^{-0.5}\approx0.393469\), while \(1-e^{-A}\approx1-e^{-0.109915}\approx0.104089\). Hence

E_\rho R\leq \frac{0.104089}{0.393469}\approx 0.2645.

This is an upper bound on posterior-averaged true risk, not a claim that the risk equals \(0.2645\). The empirical risk is only \(0.10\); the gap in the guarantee reflects both the finite sample size and the confidence and KL terms.

Worked Example: A Two-Hypothesis Posterior

Let \(\mathcal H=\{h_1,h_2\}\), with prior probabilities \(\pi(h_1)=\pi(h_2)=0.5\). A posterior assigns probabilities \(0.7\) and \(0.3\), and the two hypotheses have empirical risks \(0.10\) and \(0.40\). Take \(n=100\), \(\lambda=1\), and \(\delta=0.05\).

First average the empirical risks:

E_\rho\widehat R=0.7(0.10)+0.3(0.40)=0.07+0.12=0.19.

The posterior’s KL divergence is

\operatorname{KL}(\rho\Vert\pi) =0.7\log(0.7/0.5)+0.3\log(0.3/0.5) =0.7\log(1.4)+0.3\log(0.6) \approx0.082283.

Thus

A=1(0.19)+\frac{0.082283+\log 20}{100} =0.19+\frac{0.082283+2.995732}{100} \approx0.220780.

Since \(1-e^{-1}\approx0.632121\) and \(1-e^{-0.220780}\approx0.198107\), the bound is

E_\rho R\leq\frac{0.198107}{0.632121}\approx0.3134.

The posterior’s empirical risk is a probability-weighted average across both hypotheses. Its complexity is also the KL divergence of the whole posterior, rather than the penalty for selecting just one of the hypotheses.

Worked Example: A Point Posterior on a Low-Prior-Mass Hypothesis

Consider a finite hypothesis space with a hypothesis \(h_*\) that has prior mass \(0.1\). Let \(\rho\) put all its mass on \(h_*\), whose empirical risk is \(0.20\). With \(n=40\), \(\lambda=0.8\), and \(\delta=0.05\), calculate the bound for this point posterior.

For a point posterior, the KL divergence is \(\operatorname{KL}(\rho\Vert\pi)=\log(1/0.1)=\log 10\approx2.302585\). Therefore

A=0.8(0.20)+\frac{\log 10+\log 20}{40} =0.16+\frac{2.302585+2.995732}{40} \approx0.292458.

The transform has denominator \(1-e^{-0.8}\approx0.550671\), and its numerator is \(1-e^{-0.292458}\approx0.253574\). Thus

R(h_*)\leq \frac{0.253574}{0.550671} \approx0.4605.

The small prior mass has a visible cost: the KL term is \(\log 10\). A low empirical risk alone does not determine the guarantee; how much prior mass was assigned to the selected hypothesis also matters.

Reading the Guarantee Carefully

Several features of the result are important in practice:

It is simultaneous over posteriors. The posterior may depend on the observed sample, because the event used in the proof is an event about the prior integral that holds before any posterior is selected.
The prior must be sample-independent. The proof integrates the exponential moment with respect to \(\pi\) before applying the change-of-measure inequality. If the prior is selected using the same data without an appropriate adjustment, this argument does not justify the stated bound.
The loss scale matters. The chord inequality used here is for losses in \([0,1]\). A loss bounded in \([0,B]\) must first be rescaled, or the bound must be written with the corresponding range-dependent transform.
The temperature is fixed for this statement. For each fixed \(\lambda>0\), the probability guarantee is as stated. Taking a data-dependent or selected temperature requires a valid additional argument; it does not follow merely from having a bound for each fixed value.

Common pitfall: It is tempting to read the result as \(E_\rho R\leq E_\rho\widehat R+\{\operatorname{KL}+\log(1/\delta)\}/n\). That is not Catoni’s bound: the empirical-risk and complexity terms enter the exponent, and the result is then passed through the nonlinear inverse transform. The correction is to keep the complete quantity \(A=\lambda E_\rho\widehat R+(\operatorname{KL}+\log(1/\delta))/n\) together and use \((1-e^{-A})/(1-e^{-\lambda})\). Also, the KL penalty belongs to the posterior distribution as a whole; it is not automatically the penalty for its most likely hypothesis.

Key takeaway: For bounded losses, the exponential-moment argument gives a high-probability event on which every posterior obeys a risk bound. Its controlling quantity is the posterior empirical risk weighted by \(\lambda\), plus KL complexity and confidence costs divided by \(n\); the exponential transform converts that trade-off into a true-risk guarantee.

Check Your Understanding

Answer each question by referring to the assumptions or steps in the derivation.

Where is the restriction \(\ell(h,Z)\in[0,1]\) used in the exponential-moment argument?
Why does the high-probability event in the proof support a posterior chosen after observing the sample?
For fixed \(\lambda\), which two posterior-dependent quantities enter the exponent in Catoni’s bound, and how does each affect the guarantee?
What changes in the numerical bound if a posterior’s KL divergence increases while its empirical risk and all other values remain fixed?
Why does a point posterior on a hypothesis of prior mass \(0.1\) have KL divergence \(\log 10\)?