PAC-Bayes Bounds for Unbounded Losses

Why Unbounded Losses Need Tail Conditions

A PAC-Bayes upper bound compares a posterior-averaged population risk with its empirical counterpart. For bounded losses, concentration arguments control how often the empirical risk substantially underestimates the population risk. When losses are unbounded, a rare observation can have a very large value, and bounded-loss arguments no longer apply automatically. The relevant question is not simply whether the loss is unbounded, but whether its deviations have a sufficiently controlled exponential moment.

This tutorial gives a high-probability bound under a one-sided exponential-moment condition and then specializes it to sub-gamma deviations. The condition is stated for the deviation $R(h)-\ell(h,Z)$: it controls the event that observed loss is unusually small relative to its expectation, which is the direction that threatens an upper bound on risk.

Setup and Exponential-Moment Assumption

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$. A predictor $h$ has measurable loss $\ell(h,z)$, population risk $R(h)=E[\ell(h,Z)]$, and empirical risk $\hat R_n(h)=n^{-1}\sum_{i=1}^n\ell(h,Z_i)$. Assume these expectations exist and are finite for the predictors under consideration. Let $\pi$ be a prior distribution on predictors, fixed independently of the sample, and let $Q$ be a posterior distribution. Write $\mathrm{KL}(Q\|\pi)$ for their Kullback–Leibler divergence; it is infinite unless $Q$ is absolutely continuous with respect to $\pi$.

Exponential-moment assumption: For a fixed $\lambda>0$, suppose there is a finite constant $\psi(\lambda)$ such that, for $\pi$-almost every $h$, $$ E\!\left[\exp\{\lambda(R(h)-\ell(h,Z))\}\right]\leq \exp\{\psi(\lambda)\}. $$ The expectation is over a fresh observation $Z\sim P$. The same $\lambda$ and $\psi(\lambda)$ must work for all predictors in the prior’s support.

This is a one-sided condition. It does not require a moment-generating function for both signs of the centered loss, nor does it bound the loss itself. However, it is a genuine requirement: an unbounded loss need not satisfy it with a finite, useful $\psi(\lambda)$.

Worked Example: An Unbounded Gaussian Loss

Suppose there is one predictor and its loss has distribution $L=\ell(h,Z)\sim N(\mu,\sigma^2)$. Its risk is $R(h)=\mu$, and $R(h)-L\sim N(0,\sigma^2)$. The Gaussian moment-generating function gives, for every $\lambda>0$, $$ E[\exp\{\lambda(R(h)-L)\}]=\exp(\lambda^2\sigma^2/2). $$ Thus the condition holds with $\psi(\lambda)=\lambda^2\sigma^2/2$, although the loss is unbounded. For $n=100$, $\sigma=2$, and $\delta=0.05$, the bound proved below has excess-risk term $$ \frac{\log(1/\delta)}{n\lambda}+\frac{\lambda\sigma^2}{2}. $$ Choosing $\lambda=\sqrt{2\log(20)/(100\cdot4)}\approx0.1224$ makes the two terms equal. Each is approximately $0.2448$, so the resulting upper bound is $E_Q R\leq E_Q\hat R_n+0.4896$ with probability at least $0.95$. This example illustrates the moment condition; a Gaussian loss can take negative values and is not a conventional nonnegative loss.

A High-Probability PAC-Bayes Bound

The bound follows by combining a change-of-measure inequality with Markov’s inequality. The change-of-measure inequality says that for a measurable function $g$ and any $Q\ll\pi$, $$ E_Q[g]-\mathrm{KL}(Q\|\pi)\leq \log E_\pi[\exp(g)]. $$ When the quantities are finite, this follows by writing the density $q=dQ/d\pi$ and applying Jensen’s inequality: $$ E_Q[g]-\mathrm{KL}(Q\|\pi) =E_Q\!\left[\log\frac{\exp(g)}{q}\right] \leq \log E_Q\!\left[\frac{\exp(g)}{q}\right] =\log E_\pi[\exp(g)]. $$ The inequality extends in the usual extended-value sense when the right side is finite.

Theorem: Suppose the observations are iid, the prior $\pi$ is independent of them, and the exponential-moment assumption holds for a fixed $\lambda>0$. Then, with probability at least $1-\delta$ over the sample, simultaneously for every posterior $Q\ll\pi$ with finite $\mathrm{KL}(Q\|\pi)$, $$ E_Q[R(h)]\leq E_Q[\hat R_n(h)] +\frac{\mathrm{KL}(Q\|\pi)+\log(1/\delta)}{n\lambda} +\frac{\psi(\lambda)}{\lambda}. $$

Proof. For a realized sample, define $$ S=\int \exp\!\left\{\lambda\sum_{i=1}^n(R(h)-\ell(h,Z_i))\right\}\,\pi(dh). $$ By Tonelli’s theorem, independence of the observations, and the exponential-moment assumption, $$ E[S] =\int \prod_{i=1}^n E\!\left[\exp\{\lambda(R(h)-\ell(h,Z_i))\}\right]\,\pi(dh) \leq \exp\{n\psi(\lambda)\}. $$ Markov’s inequality therefore gives $P(S>\exp\{n\psi(\lambda)\}/\delta)\leq\delta$. On the complementary event, apply the change-of-measure inequality with $g(h)=\lambda n(R(h)-\hat R_n(h))$. It yields $$ \lambda n E_Q[R(h)-\hat R_n(h)] \leq \mathrm{KL}(Q\|\pi)+\log S \leq \mathrm{KL}(Q\|\pi)+n\psi(\lambda)+\log(1/\delta). $$ Dividing by $n\lambda$ proves the assertion. The event was defined using $S$, not $Q$, so the conclusion holds simultaneously for all such posteriors, including posteriors chosen after observing the data. $\square$

The proof requires the exponential-moment bound only under the prior and transfers it to arbitrary posteriors at a cost measured by $\mathrm{KL}(Q\|\pi)$. Its probability guarantee is over the observed sample. The theorem does not say that every unbounded loss satisfies the assumption, or that the resulting constants are informative whenever the moment exists.

Worked Example: Exponential Losses and a Data-Dependent Posterior

Consider two predictors with losses distributed as exponential random variables, with respective means $\mu_1=1$ and $\mu_2=2$. For an exponential loss $L$ of mean $\mu$, direct integration gives $$ E[\exp\{\lambda(\mu-L)\}] =\frac{\exp(\lambda\mu)}{1+\lambda\mu}, \qquad \log E[\exp\{\lambda(\mu-L)\}] =x-\log(1+x),\quad x=\lambda\mu. $$ For $x\geq0$, $x-\log(1+x)\leq x^2/2$: the difference $x^2/2-x+\log(1+x)$ is zero at zero and has derivative $x^2/(1+x)\geq0$. Thus, for both predictors and $\lambda=0.2$, a common choice is $\psi(\lambda)=\lambda^2(2)^2/2=0.08$.

Let the prior assign probability $1/2$ to each predictor, take $n=50$, and set $\delta=0.05$. If the posterior puts all its mass on predictor 2, its KL divergence from the prior is $\log 2$. The theorem’s excess-risk term is $$ \frac{\log 2+\log 20}{50(0.2)}+\frac{0.08}{0.2} =\frac{3.6889}{10}+0.4 \approx0.7689. $$ Consequently, on the theorem’s event, this posterior’s population risk is at most its empirical risk plus $0.7689$. If its observed empirical risk is $1.6$, the resulting upper bound is $2.3689$, consistent with its true risk of $2$. The posterior could have been selected after seeing the data because the guarantee holds simultaneously for all $Q$.

Sub-Gamma Deviations

A useful way to specify the exponential-moment assumption is through a sub-gamma bound. Here it is imposed on the one-sided centered deviation $R(h)-\ell(h,Z)$, uniformly over predictors. The variance factor $v$ and scale $c$ are fixed constants; no data-dependent or predictor-specific variance refinement is being claimed.

Definition: A centered random variable $Y$ is sub-gamma on the right with variance factor $v\geq0$ and scale $c\geq0$ if, for $0<\lambda<1/c$, $$ \log E[\exp(\lambda Y)]\leq \frac{\lambda^2v}{2(1-c\lambda)}. $$ When $c=0$, the condition is required for every $\lambda>0$.

If $Y=R(h)-\ell(h,Z)$ satisfies this condition with the same $v,c$ for $\pi$-almost every $h$, substitute $\psi(\lambda)=\lambda^2v/[2(1-c\lambda)]$ into the theorem. For any fixed $0<\lambda<1/c$, with probability at least $1-\delta$, simultaneously for all eligible $Q$, $$ E_Q[R(h)]\leq E_Q[\hat R_n(h)] +\frac{\mathrm{KL}(Q\|\pi)+\log(1/\delta)}{n\lambda} +\frac{\lambda v}{2(1-c\lambda)}. $$ This is a direct consequence of the theorem, not an additional concentration argument. The parameter $\lambda$ must lie in the range where the moment bound holds. Choosing it involves a trade-off: a larger $\lambda$ reduces the complexity term but increases the tail term, particularly near $1/c$.

Worked Example: A Heavy-Tailed Loss Fails the Moment Condition

Let a single predictor have a centered Student $t$ loss with three degrees of freedom. Its mean exists and is zero, so $R(h)=0$. The density has a polynomial left tail: for sufficiently large $u$, it is bounded below by a positive constant times $u^{-4}$. For any $\lambda>0$, $$ E[\exp\{\lambda(R(h)-L)\}] =E[\exp(-\lambda L)] \geq C\int_A^\infty \exp(\lambda u)u^{-4}\,du =\infty $$ for suitable constants $C>0$ and $A>0$. The integral diverges because exponential growth dominates polynomial decay. Hence no finite $\psi(\lambda)$ exists for any positive $\lambda$, and neither the exponential-moment theorem nor its sub-gamma specialization applies. This does not rule out every possible risk guarantee; it shows that a proof relying on this particular exponential moment cannot be used here.

How This Relates to Bounded-Loss Bounds

If losses lie in an interval $[a,b]$, Hoeffding’s lemma gives the exponential-moment condition with $\psi(\lambda)=\lambda^2(b-a)^2/8$. The theorem then has tail term $\lambda(b-a)^2/8$, recovering the familiar bounded-range form. For unbounded losses there is no fixed range width to insert. A separate tail assumption must supply a finite $\psi(\lambda)$, and its value determines the resulting guarantee.

For example, a nonnegative unbounded loss does have a finite one-sided exponential moment at each fixed $\lambda>0$ whenever its mean is finite, because $R-L\leq R$. But the elementary bound $E[\exp\{\lambda(R-L)\}]\leq \exp(\lambda R)$ depends on the risk itself and may be too weak or nonuniform across predictors. A useful PAC-Bayes guarantee needs a suitable common moment bound, not merely the bare fact that the loss is nonnegative.

Common Pitfall

A common error is to apply a bounded-loss PAC-Bayes result to an unbounded loss because its expectation is finite, or because the loss is nonnegative. Finite expectation alone does not guarantee the exponential-moment condition needed by the proof; signed heavy-tailed losses can have an infinite moment in the required direction. The correction is to identify the exact centered deviation $R(h)-\ell(h,Z)$, verify a uniform exponential-moment or sub-gamma bound for it, and only then invoke the theorem. If that verification fails, a different assumption and proof are needed.

Key takeaway: Unboundedness is not itself a reason a PAC-Bayes bound must fail. The decisive issue here is whether the one-sided centered loss has a controlled exponential moment, uniformly under the prior. The bound then pays for the posterior’s departure from the prior through its KL divergence.

Check Your Understanding

Check whether you can identify both the required assumption and the role it plays in the bound.

Which direction of the centered loss deviation is controlled by the exponential-moment assumption, and why is it relevant to an upper bound on risk?
In the theorem, why does the high-probability event hold simultaneously for all posteriors, including data-dependent ones?
For a sub-gamma deviation with variance factor $v$ and scale $c$, what range of $\lambda$ is allowed, and what tail term enters the PAC-Bayes bound?
Why does finite mean of a nonnegative unbounded loss not necessarily give a useful uniform exponential-moment bound?
What calculation shows that the centered Student $t$ loss in the example fails the required assumption?