PAC-Bayesian Bounds for Neural Predictors

From a Single Network to a Distribution of Networks

A neural-network predictor is often assessed through one fitted parameter vector. PAC-Bayesian analysis instead places a probability distribution over parameter vectors and studies the risk obtained by drawing a network from that distribution. This formulation can describe deliberate randomization around a fitted network, and it gives a way to compare a posterior distribution with a reference distribution chosen before observing the training sample.

The resulting bound has four interpretable parts: the posterior’s empirical risk, a complexity cost measuring how far the posterior moves from the prior, a confidence penalty, and a tuning term. The central point is that the posterior may depend on the data, while the prior must not. We first state the setting and then derive the bound under bounded loss.

Definition: Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $D$, and let $S=(Z_1,\ldots,Z_n)$. For a neural-network parameter $w$ and a measurable loss $\ell(w,z)\in[0,1]$, define the population risk $R(w)=E_{Z\sim D}[\ell(w,Z)]$ and empirical risk $\hat R_S(w)=n^{-1}\sum_{i=1}^n\ell(w,Z_i)$. For a probability distribution $Q$ over parameters, define $R(Q)=E_{w\sim Q}[R(w)]$ and $\hat R_S(Q)=E_{w\sim Q}[\hat R_S(w)]$. The prior $P$ is a probability distribution over parameters specified independently of $S$; the posterior $Q$ may depend on $S$.

The risks $R(Q)$ and $\hat R_S(Q)$ are risks for a randomized predictor: draw $w\sim Q$, then predict using the network with parameters $w$. They are not generally the risks of the network whose parameters are the mean $E_Q[w]$. Nonlinear network outputs need not commute with averaging parameters.

The Change-of-Measure Inequality

The KL divergence measures the cost of replacing the prior by the posterior. We use the convention that $Q$ is absolutely continuous with respect to $P$, written $Q\ll P$, if every set of zero $P$-probability also has zero $Q$-probability. In that case let $r=dQ/dP$ be the density and define $\mathrm{KL}(Q\|P)=E_Q[\log r]$, provided this expectation is finite.

Lemma (change of measure): Suppose $Q\ll P$, $\mathrm{KL}(Q\|P)<\infty$, and $h$ is a bounded measurable function. Then $$ E_Q[h]\leq \mathrm{KL}(Q\|P)+\log E_P[e^h]. $$

To prove the inequality, apply Jensen’s inequality for the concave logarithm under $Q$. On the set where $r>0$, the identity $dQ=r\,dP$ gives

\begin{aligned} E_Q[h]-\mathrm{KL}(Q\|P) &=E_Q[h-\log r]\\ &\leq \log E_Q[e^{h-\log r}]\\ &=\log\int_{\{r>0\}}\frac{e^h}{r}\,dQ\\ &=\log\int_{\{r>0\}}e^h\,dP\\ &\leq \log E_P[e^h]. \end{aligned}

The last inequality is important: the integral over $\{r>0\}$ can be smaller than the integral over the whole prior space. It need not equal it, because $r$ may be zero on a set with positive $P$-probability. This proves the lemma. $\square$

A Bounded-Loss PAC-Bayesian Bound

We need an exponential bound for the difference between population and empirical risk. The relevant concentration fact is Hoeffding’s lemma. For completeness, here is the bounded-variable form used in the derivation.

Lemma (Hoeffding): If $X$ is a random variable supported on an interval $[a,b]$, then for every real $t$, $$ E[e^{t(X-E[X])}]\leq e^{t^2(b-a)^2/8}. $$

For a proof, let $\psi(t)=\log E[e^{t(X-E[X])}]$. Boundedness permits differentiation under the expectation. Under the exponentially tilted distribution with density proportional to $e^{tX}$, the second derivative $\psi''(t)$ is the variance of $X$. Any random variable supported on $[a,b]$ has variance at most $(b-a)^2/4$: since $(X-a)(b-X)\geq0$, taking expectations and rearranging gives $\operatorname{Var}(X)\leq(E[X]-a)(b-E[X])\leq(b-a)^2/4$. Thus $\psi''(t)\leq(b-a)^2/4$, while $\psi(0)=\psi'(0)=0$. Integrating this second-derivative bound from zero, for positive or negative $t$, yields $\psi(t)\leq t^2(b-a)^2/8$. $\square$

Theorem (PAC-Bayesian risk bound): Suppose the observations are independent and identically distributed from $D$, the loss is jointly measurable and takes values in $[0,1]$, and $P$ is a fixed prior independent of the sample. For any fixed $\lambda>0$ and $\delta\in(0,1)$, with probability at least $1-\delta$ over $S$, every posterior $Q\ll P$ with finite KL divergence satisfies $$ R(Q)\leq \hat R_S(Q)+\frac{\mathrm{KL}(Q\|P)+\log(1/\delta)}{\lambda n}+\frac{\lambda}{8}. $$

Here “fixed” means that $\lambda$ is selected independently of the observed sample and posterior. The event in this theorem is uniform over $Q$, so it permits a data-dependent posterior. Its uniformity does not extend to all $\lambda$ at once.

Proof. Fix a parameter $w$. Since each loss lies in $[0,1]$, Hoeffding’s lemma applied to each independent observation, with $t=-\lambda$, gives

\begin{aligned} E_S\!\left[e^{\lambda n(R(w)-\hat R_S(w))}\right] &=\prod_{i=1}^n E_{Z_i}\!\left[e^{\lambda(R(w)-\ell(w,Z_i))}\right]\\ &\leq e^{n\lambda^2/8}. \end{aligned}

Integrate this nonnegative quantity with respect to $P$. Tonelli’s theorem allows the order of expectation and integration to be exchanged, giving

E_S\!\left[E_{w\sim P}e^{\lambda n(R(w)-\hat R_S(w))}\right]\leq e^{n\lambda^2/8}.

Markov’s inequality therefore implies that, with probability at least $1-\delta$, $$ E_{w\sim P}e^{\lambda n(R(w)-\hat R_S(w))}\leq \frac{e^{n\lambda^2/8}}{\delta}. $$ Fix any sample in this event. Apply the change-of-measure lemma with $h(w)=\lambda n(R(w)-\hat R_S(w))$. This function is bounded because the loss lies in $[0,1]$. For every $Q\ll P$ with finite KL divergence, the same event gives

\lambda n\bigl(R(Q)-\hat R_S(Q)\bigr) \leq \mathrm{KL}(Q\|P)+\frac{n\lambda^2}{8}+\log(1/\delta).

Dividing by $\lambda n>0$ proves the bound. The argument applies to every such $Q$ on this one event because the change-of-measure inequality is deterministic once the sample is fixed. $\square$

Worked Calculations

Worked Example: A Discrete Posterior

Suppose a prior assigns probability $1/4$ to each of four neural networks. A posterior assigns all its mass to one of them. On a sample of $n=100$, that network makes 5 losses of 1 and 95 losses of 0. Take $\lambda=2$ and $\delta=0.1$.

The posterior empirical risk is $\hat R_S(Q)=5/100=0.05$. Since the selected network had prior probability $1/4$, the posterior-to-prior KL divergence is $\mathrm{KL}(Q\|P)=\log(1/(1/4))=\log4\approx1.3863$. The theorem gives

R(Q)\leq 0.05+ \frac{1.3863+\log 10}{2(100)}+\frac{2}{8} =0.05+\frac{3.6889}{200}+0.25 \approx 0.3184.

This is a high-probability upper bound on the selected network’s population risk. It is not a claim that its risk equals the bound.

Worked Example: A Gaussian Posterior over Network Weights

Let the two-dimensional prior be $P=N(0,I_2)$, and let the posterior be $Q=N((1,0),I_2)$. For Gaussian distributions with the same identity covariance, direct evaluation of the log density ratio gives $\mathrm{KL}(Q\|P)=\tfrac12\|(1,0)\|^2=0.5$. Suppose the posterior-averaged empirical loss on $n=500$ observations is $40/500=0.08$. With $\lambda=1$ and $\delta=0.05$,

R(Q)\leq 0.08+ \frac{0.5+\log 20}{500}+\frac18 =0.08+\frac{3.4957}{500}+0.125 \approx 0.2120.

The posterior here randomizes around a shifted Gaussian distribution of weights. Its KL cost reflects the shift from the reference prior, while its empirical-risk term averages losses over the posterior’s sampled networks.

Worked Example: Posterior Spread Also Affects KL

Keep $P=N(0,I_2)$, but take $Q=N((1,0),2I_2)$. The KL divergence between $N(m,\Sigma)$ and $N(0,I_2)$ in dimension $d$ is $\tfrac12(\|m\|^2+\operatorname{tr}(\Sigma)-d-\log\det\Sigma)$. Here $d=2$, $\|m\|^2=1$, $\operatorname{tr}(\Sigma)=4$, and $\log\det\Sigma=\log4$. Hence

\mathrm{KL}(Q\|P)=\frac12(1+4-2-\log4) =\frac12(3-1.3863)\approx0.8069.

If the empirical posterior-averaged loss is $0.10$ on $n=200$, then using $\lambda=2$ and $\delta=0.05$ gives $$ R(Q)\leq 0.10+\frac{0.8069+\log20}{400}+0.25 \approx 0.10+\frac{3.8026}{400}+0.25 \approx 0.3595. $$

Compared with a posterior having the same mean but identity covariance, the greater spread raises the KL cost. The empirical-risk term must also be evaluated for this wider posterior; it cannot be inferred from the empirical risk at the posterior mean.

How to Read the Bound—and a Common Pitfall

The inequality balances fit and complexity. A posterior concentrated on networks with low empirical risk can still yield a weak guarantee if its KL divergence from the prior is large. Conversely, a posterior close to the prior has a smaller complexity penalty but may average over networks with higher empirical loss. The confidence term grows as $\delta$ decreases, reflecting a request for a higher-probability guarantee.

The theorem assumes bounded loss. Squared loss, for example, is not automatically bounded, so this result cannot be applied to it without additional conditions or a different concentration argument. The neural-network architecture can be fixed in advance, or its alternatives can be included in a larger parameter space with a suitable prior, but the prior itself must be chosen independently of the training sample.

Pitfall: choosing $\lambda$ after seeing the posterior. The proof uses Markov’s inequality for one fixed $\lambda$, and the resulting event depends on that choice. It does not justify optimizing $\lambda$ after observing a data-dependent KL divergence. Use a predetermined $\lambda$ for this theorem; a simultaneous tuning-parameter result needs a separate uniform argument and its corresponding correction.
Pitfall: treating the posterior as though it had the prior’s full support. In the change-of-measure proof, the integral under $P$ is first restricted to $\{dQ/dP>0\}$, then bounded above by the full prior integral. Replacing this inequality with an equality is not generally valid.
Pitfall: interpreting $R(Q)$ as the risk at average weights. The theorem controls the risk of a network drawn from $Q$. For nonlinear neural predictors, that is generally different from evaluating a single network at $E_Q[w]$.

Key takeaway: For bounded loss, a sample-independent prior and a posterior over neural parameters give a high-probability risk bound with empirical posterior risk, KL complexity, confidence, and tuning terms. The posterior may be data-dependent; the stated tuning parameter may not.

Check Your Understanding

Use the definitions and theorem to check each point.

Why can the posterior depend on the training sample in the theorem, while the prior cannot?
Which step in the change-of-measure proof requires $Q\ll P$, and why may the integral over $\{dQ/dP>0\}$ be strictly smaller than the full prior integral?
For a loss in $[0,1]$, identify which term in the theorem is the empirical-risk term and which is the KL complexity penalty.
Why does the theorem not justify selecting $\lambda$ after observing a data-dependent posterior’s KL divergence?
In general, does $R(Q)$ equal the risk of the network with parameters $E_Q[w]$? Explain.