Variance-Sensitive PAC-Bayes Bounds

Why account for variability?

A range-only concentration bound treats a loss that is almost constant across observations much like one that frequently moves across its entire allowed range. Bernstein concentration uses more information: the fluctuation of the loss around its mean. In PAC-Bayes analysis, this information can be averaged over a posterior distribution on predictors, giving a guarantee whose variance term reflects the predictors receiving posterior mass.

The result below assumes losses in $[0,1]$. This boundedness assumption is stated explicitly because the moment argument depends on it; bounds for unbounded losses require different tail conditions. The guarantee is simultaneous over posteriors, including posteriors selected using the observed sample.

Setup and definitions

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$, and let $\mathcal H$ be a measurable hypothesis space. For each $h\in\mathcal H$, suppose the loss $\ell(h,Z)$ is jointly measurable and satisfies $0\leq \ell(h,Z)\leq 1$ almost surely. Let $\pi$ be a fixed prior probability distribution on $\mathcal H$, independent of the sample. A posterior $\rho$ is any probability distribution on $\mathcal H$, possibly chosen after observing the sample.

Definition: For a predictor $h$, its population risk, empirical risk, and population loss variance are $$ R(h)=E_{Z\sim P}[\ell(h,Z)],\qquad \widehat R(h)=\frac{1}{n}\sum_{i=1}^n\ell(h,Z_i),\qquad V(h)=\operatorname{Var}_{Z\sim P}(\ell(h,Z)). $$ For a posterior $\rho$, define $$ R(\rho)=E_{h\sim\rho}[R(h)],\qquad \widehat R(\rho)=E_{h\sim\rho}[\widehat R(h)],\qquad V(\rho)=E_{h\sim\rho}[V(h)]. $$ Here $V(\rho)$ is the posterior average of the individual predictors’ population variances, not the variance of the loss after mixing predictors.

The relative entropy of $\rho$ with respect to $\pi$ is $\operatorname{KL}(\rho\|\pi)=\int\log(d\rho/d\pi)\,d\rho$ when $\rho$ is absolutely continuous with respect to $\pi$; otherwise it is infinite. This complexity term penalizes posteriors that depart substantially from the prior.

The Bernstein PAC-Bayes bound

For $0\leq\lambda<3$, the Bernstein moment bound for a centered random variable with absolute value at most one is $$ \log E[\exp(\lambda Y)]\leq \frac{\lambda^2 E[Y^2]}{2(1-\lambda/3)}. $$ The denominator captures the bounded range, while $E[Y^2]$ captures variability. Applied to $Y=R(h)-\ell(h,Z)$, this controls the upward generalization gap $R(h)-\widehat R(h)$.

Theorem: Under the setup above, fix $0<\lambda<3$ and $0<\delta<1$. With probability at least $1-\delta$ over the sample, every posterior $\rho$ with finite $\operatorname{KL}(\rho\|\pi)$ satisfies $$ R(\rho)\leq \widehat R(\rho) +\frac{\operatorname{KL}(\rho\|\pi)+\log(1/\delta)}{\lambda n} +\frac{\lambda V(\rho)}{2(1-\lambda/3)}. $$

The temperature $\lambda$ in this statement is fixed before the sample-dependent posterior is evaluated. The theorem uses the population variance $V(\rho)$. A sample variance may estimate this quantity, but substituting it directly does not follow from the theorem.

Proof of the theorem

First, the scalar moment bound follows directly from the exponential series. If $E[Y]=0$ and $|Y|\leq1$, then for every integer $k\geq2$, $E[|Y|^k]\leq E[Y^2]$. Also $k!\geq 2\cdot 3^{k-2}$ for $k\geq2$. For $0\leq\lambda<3$, these facts give $$ E[e^{\lambda Y}] \leq 1+E[Y^2]\sum_{k=2}^{\infty}\frac{\lambda^k}{k!} \leq 1+\frac{\lambda^2 E[Y^2]}{2(1-\lambda/3)}. $$ Taking logarithms and using $\log(1+x)\leq x$ for $x\geq0$ proves the stated moment bound.

For fixed $h$, the centered variables $R(h)-\ell(h,Z_i)$ are independent, have mean zero, absolute value at most one, and variance $V(h)$. Applying the moment bound to each and multiplying the resulting expectations yields $$ E_{Z_1,\ldots,Z_n}\left[ \exp\left\{ \lambda n\bigl(R(h)-\widehat R(h)\bigr) -\frac{n\lambda^2 V(h)}{2(1-\lambda/3)} \right\}\right]\leq1. $$ Integrating this inequality with respect to the fixed prior and applying Tonelli’s theorem to the nonnegative integrand gives an expectation at most one for the corresponding prior integral. Markov’s inequality therefore implies that, with probability at least $1-\delta$, $$ \log\int \exp\left\{ \lambda n\bigl(R(h)-\widehat R(h)\bigr) -\frac{n\lambda^2 V(h)}{2(1-\lambda/3)} \right\}\,d\pi(h) \leq \log(1/\delta). $$

On this event, the change-of-measure inequality says that the posterior average of the exponent’s integrand function is at most its log prior exponential integral plus $\operatorname{KL}(\rho\|\pi)$. Explicitly, for any integrable function $g$, $$ E_\rho[g]\leq \operatorname{KL}(\rho\|\pi)+\log E_\pi[e^g]. $$ This follows by Jensen’s inequality applied under $\rho$ to $e^g(d\pi/d\rho)$; if absolute continuity fails, the right side is infinite. Apply it to the function inside the exponential above. The resulting inequality is $$ \lambda n\bigl(R(\rho)-\widehat R(\rho)\bigr) -\frac{n\lambda^2V(\rho)}{2(1-\lambda/3)} \leq \operatorname{KL}(\rho\|\pi)+\log(1/\delta). $$ Dividing by $\lambda n>0$ and rearranging proves the theorem. Since the event was defined using a prior integral and not a particular posterior, the conclusion holds for every posterior on that same event. $\square$

Worked examples

Worked Example: A low-variance Bernoulli loss

Suppose a fixed predictor has loss $1$ with probability $0.1$ and loss $0$ with probability $0.9$. Its risk is $R=0.1$, and its variance is $$ V=0.1(1-0.1)^2+0.9(0-0.1)^2 =0.081+0.009=0.09. $$ Assume the complexity and confidence contribution divided by sample size is $A=0.02$, and choose $\lambda=0.8$, which is below $3$. The theorem’s excess-risk penalty is $$ \frac{A}{\lambda}+\frac{\lambda V}{2(1-\lambda/3)} =\frac{0.02}{0.8}+\frac{0.8(0.09)}{2(1-0.8/3)} =0.025+\frac{0.072}{1.466666\ldots} \approx 0.0741. $$ For comparison, the range-only Hoeffding penalty optimized over its temperature is $\sqrt{A/2}=0.1$. The variance-sensitive penalty at this chosen temperature is smaller. This calculation illustrates the benefit when variability is low; it does not assert that the displayed temperature is optimal.

Worked Example: Choosing a temperature from a fixed variance bound

Suppose $n=200$, $\delta=0.05$, and the posterior under consideration has risk variance $V(\rho)=0.01$. Take $A=\log(1/\delta)/n=\log(20)/200$, so $$ A=\frac{2.9957322736\ldots}{200}=0.01497866137\ldots. $$ For a fixed variance value $v=0.01$, the penalty as a function of temperature is $A/\lambda+\lambda v/[2(1-\lambda/3)]$. Differentiating and setting the derivative to zero gives $$ -\frac{A}{\lambda^2}+\frac{v}{2(1-\lambda/3)^2}=0, \qquad \lambda=\frac{t}{1+t/3},\qquad t=\sqrt{\frac{2A}{v}}. $$ Here $t=\sqrt{2.9957322736\ldots}=1.730818\ldots$, so $\lambda\approx1.0976$, which is in the permitted interval. Substituting this value, the minimized penalty is $$ \sqrt{2Av}+\frac{A}{3} =\sqrt{2(0.01497866137\ldots)(0.01)} +\frac{0.01497866137\ldots}{3} \approx 0.02230107. $$ Thus, rounding the penalty upward to five decimal places gives $0.02231$, not $0.02230$. If the empirical risk is $0.18$, the exact bound is approximately $0.20230107$; using the penalty rounded upward to five decimal places gives the valid, slightly looser bound $0.20231$. This numerical choice is justified when the variance value is available independently of the sample or is a valid fixed upper bound. Choosing a temperature after inspecting a posterior’s sample variance requires an additional temperature-selection argument.

Worked Example: Posterior-averaged variance is not mixture variance

Let the hypothesis space contain two predictors. Predictor $h_0$ always has loss $0$, and predictor $h_1$ always has loss $1$, regardless of the observed $Z$. Let $\rho$ assign probability $1/2$ to each. For each predictor separately, the loss is constant across observations, so $V(h_0)=V(h_1)=0$. Consequently, $$ V(\rho)=\tfrac12 V(h_0)+\tfrac12 V(h_1)=0. $$ If one instead first randomly draws a predictor from $\rho$ and then looks at its loss, that mixed loss is $0$ or $1$ with equal probability and has variance $1/4$. That $1/4$ is variability between predictors, not variability across observations for a fixed predictor. In this example each predictor’s empirical risk equals its population risk exactly, which is consistent with the zero posterior-averaged loss variance in the theorem.

How to interpret empirical variability

For a fixed predictor, the sample variance of its observed losses is a natural diagnostic for $V(h)$; averaging such sample variances over a posterior is likewise a diagnostic for posterior-averaged variability. If those quantities are small, Bernstein-based bounds can be substantially tighter than bounds using only the loss range. However, the theorem proved here contains the population quantity $V(\rho)$. Replacing it with the observed sample variance without a separate concentration argument can make a claimed guarantee invalid. An empirical-variance guarantee must establish an appropriate upper confidence bound or use a proved empirical-Bernstein PAC-Bayes inequality.

Comparison with a range-only bound

For losses in $[0,1]$, Hoeffding’s lemma gives a log moment bound of $\lambda^2/8$, without a variance factor. The same PAC-Bayes steps therefore yield a penalty $A/\lambda+\lambda/8$, where $A=(\operatorname{KL}(\rho\|\pi)+\log(1/\delta))/n$, for a fixed temperature. Its optimized value is $\sqrt{A/2}$. The Bernstein penalty instead has a variance-dependent term and a range correction in its denominator. When the posterior-averaged loss variance is small, a suitable temperature can reduce the bound; when it is large, the range still limits how sharply concentration can improve.

Key takeaway: Bernstein concentration replaces a range-only fluctuation penalty with one involving $V(\rho)$, the posterior average of individual population loss variances. The high-probability PAC-Bayes event remains valid for all posteriors, but the temperature must be handled carefully and empirical variance requires its own justification.

Common pitfalls

Plugging in sample variance without a theorem. The proved bound uses population variance. A small observed sample variance alone does not certify that population variance is small.
Confusing two kinds of variance. $V(\rho)$ averages variability over observations for fixed predictors; it does not include differences in average loss between predictors.
Optimizing after seeing the data for free. The theorem is stated for a fixed temperature. Data-dependent temperature selection needs a valid adaptation argument, such as a suitable prior over temperatures and its associated complexity cost.
Ignoring the range condition. The displayed Bernstein moment argument assumes losses in $[0,1]$. It cannot be applied unchanged to unbounded losses.

Check Your Understanding

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

In the theorem, what is averaged over predictors in $V(\rho)$, and what is held fixed when each variance is computed?
Why does the proof require $0\leq\ell(h,Z)\leq1$? Identify where that condition enters the moment argument.
For $A>0$ and a fixed variance value $v>0$, derive the stationary temperature by differentiating $A/\lambda+\lambda v/[2(1-\lambda/3)]$.
Why does the simultaneous event in the theorem allow a sample-dependent posterior, while the stated temperature remains fixed?
What additional justification is needed before replacing population variance with empirical sample variance in a reported bound?