Tutorials › Statistical Learning (Graduate) › The Change-of-Measure Inequality

Home  /  Tutorials  /  PAC-Bayesian Generalization

PAC-Bayesian Generalization · Tutorial 347 of 989

The Change-of-Measure Inequality

Learn why a posterior expectation is bounded by a log moment-generating function under the prior plus a KL-divergence penalty.

Advanced 11 min read

What You'll Learn

  • Define KL divergence between a posterior and a prior, including when it is infinite.
  • Prove nonnegativity of KL divergence using a Radon–Nikodym density.
  • Derive the change-of-measure inequality from the variational formula for log moment-generating functions.
  • Identify the exponentially tilted posterior that attains equality in the variational formula.
  • Calculate posterior expectation bounds and interpret their KL-divergence cost.
  • Recognize why a KL penalty is not, by itself, an additive bound on posterior expectations.

Why Changing Measures Has a Cost

In PAC-Bayesian analysis, a prior \(\Pi\) describes a reference distribution over predictors, while a posterior \(\rho\) may place more weight on predictors that appear useful. This change of weights can increase the average of a function \(g\), such as a loss or a risk. The change-of-measure inequality quantifies how large that increase can be using two ingredients: the log moment-generating function of \(g\) under \(\Pi\), and the Kullback–Leibler divergence from \(\rho\) to \(\Pi\).

The inequality is deterministic once \(\Pi\), \(\rho\), and \(g\) are fixed. In applications, a posterior can depend on observed data; the inequality still applies to the resulting measures for each fixed data set. It does not, by itself, give a probability statement about data or a bound on the difference between empirical and population risk.

Definition: Let \(\rho\) and \(\Pi\) be probability measures on the same measurable space. If \(\rho\) is absolutely continuous with respect to \(\Pi\), write \(f=d\rho/d\Pi\) and define \(\operatorname{KL}(\rho\|\Pi)=\int f\log f\,d\Pi\), with \(0\log 0=0\). If \(\rho\) is not absolutely continuous with respect to \(\Pi\), set \(\operatorname{KL}(\rho\|\Pi)=+\infty\). The value of this integral may also be \(+\infty\).

The direction of the divergence matters: \(\operatorname{KL}(\rho\|\Pi)\) measures the cost of using \(\rho\) in place of the reference measure \(\Pi\). A posterior that assigns positive probability to a set to which the prior assigns zero probability has infinite divergence.

Nonnegativity of KL Divergence

The change-of-measure result rests on nonnegativity of KL divergence. The density used in its proof must be the density of the first measure with respect to the second.

Result: For probability measures \(\rho\) and \(\Pi\), \(\operatorname{KL}(\rho\|\Pi)\geq 0\).

Proof. If \(\rho\) is not absolutely continuous with respect to \(\Pi\), the divergence is \(+\infty\), so the claim holds. Otherwise let \(f=d\rho/d\Pi\). The function \(\phi(x)=x\log x\), extended continuously by \(\phi(0)=0\), is convex on \([0,\infty)\). Since \(\int f\,d\Pi=1\), Jensen's inequality gives

$$ \operatorname{KL}(\rho\|\Pi) =\int f\log f\,d\Pi \geq \left(\int f\,d\Pi\right)\log\left(\int f\,d\Pi\right) =1\log 1=0. $$

The inequality remains valid if the integral on the left is infinite. \(\square\)

The Change-of-Measure Inequality

For a bounded measurable function \(g\), its exponential moment under the prior is \(E_\Pi[e^g]\). It is finite and strictly positive. The log of this moment is the variational quantity that balances a posterior's average of \(g\) against its KL cost.

Theorem (Change-of-Measure Inequality): Let \(\Pi\) and \(\rho\) be probability measures on a measurable space, and let \(g\) be bounded and measurable. If \(\operatorname{KL}(\rho\|\Pi)<\infty\), then \[ E_\rho[g]\leq \operatorname{KL}(\rho\|\Pi)+\log E_\Pi[e^g]. \]

Proof. Define \(Z=E_\Pi[e^g]\), which satisfies \(0<Z<\infty\), and define a probability measure \(\Pi_g\) by its density with respect to \(\Pi\):

$$ \frac{d\Pi_g}{d\Pi}=\frac{e^g}{Z}. $$

Because \(g\) is bounded, this density is positive and bounded above and below by positive constants. In particular, \(\rho\ll\Pi_g\), and the log-density identity gives

$$ \operatorname{KL}(\rho\|\Pi_g) =\operatorname{KL}(\rho\|\Pi)-E_\rho[g]+\log Z. $$

All terms are finite: the KL divergence to \(\Pi\) is finite by assumption, and \(g\) is bounded. Nonnegativity of \(\operatorname{KL}(\rho\|\Pi_g)\) therefore implies \[ E_\rho[g]\leq \operatorname{KL}(\rho\|\Pi)+\log Z, \] which is the claimed inequality. \(\square\)

Worked Example: A Three-Predictor Prior

Let the predictor space be \(\{1,2,3\}\), with prior probabilities \((1/2,1/3,1/6)\). Take \(\rho=\Pi\), and let \(g\) have values \((0,1,2)\). Calculate the posterior expectation and the right-hand side of the inequality.

Since \(\rho=\Pi\), the divergence is zero. The expectation is

$$ E_\rho[g]=\frac12(0)+\frac13(1)+\frac16(2)=\frac23\approx0.6667. $$

The prior exponential moment is

$$ E_\Pi[e^g]=\frac12+\frac{e}{3}+\frac{e^2}{6} \approx 0.5000+0.9061+1.2315=2.6376. $$

Thus \(\log E_\Pi[e^g]\approx0.9699\), and the inequality reads \(0.6667\leq0+0.9699\). This example also shows that the log moment-generating function can be larger than the prior average of \(g\): it accounts for the upper values of \(g\) exponentially.

The Variational Formula and Its Equality Case

The inequality is one side of an exact variational identity. For bounded measurable \(g\), define \(\Pi_g\) as above. For every \(\rho\) with finite KL divergence, the proof established the identity \(\ E_\rho[g]-\operatorname{KL}(\rho\|\Pi)=\log E_\Pi[e^g]-\operatorname{KL}(\rho\|\Pi_g)\). Taking a supremum over \(\rho\) gives the formula below.

Theorem (Variational Formula for the Log Moment-Generating Function): For bounded measurable \(g\), \[ \log E_\Pi[e^g] =\sup_{\rho:\,\operatorname{KL}(\rho\|\Pi)<\infty} \left\{E_\rho[g]-\operatorname{KL}(\rho\|\Pi)\right\}. \] The supremum is attained at the exponentially tilted measure \(\rho=\Pi_g\), whose density is \(e^g/E_\Pi[e^g]\) with respect to \(\Pi\).

Derivation. For every admissible \(\rho\), the identity just established and KL nonnegativity yield

$$ E_\rho[g]-\operatorname{KL}(\rho\|\Pi) =\log E_\Pi[e^g]-\operatorname{KL}(\rho\|\Pi_g) \leq\log E_\Pi[e^g]. $$

For \(\rho=\Pi_g\), its KL divergence relative to \(\Pi\) is finite because \(g\) is bounded, and \(\operatorname{KL}(\Pi_g\|\Pi_g)=0\). Substitution in the identity gives equality. This proves both the supremum formula and its attainment. \(\square\)

Worked Example: The Tilt That Attains Equality

Let \(\Pi\) assign probabilities \((1/4,3/4)\) to two outcomes, and let \(g=(\log 3,0)\). The unnormalized tilted probabilities are \((3/4,3/4)\), so \(E_\Pi[e^g]=3/2\), and the normalized tilt is \(\rho=(1/2,1/2)\).

Its expectation and divergence are

$$ E_\rho[g]=\frac12\log 3, \qquad \operatorname{KL}(\rho\|\Pi) =\frac12\log\frac{1/2}{1/4}+\frac12\log\frac{1/2}{3/4} =\frac12\log 2+\frac12\log\frac23 =\frac12\log\frac43. $$

Consequently,

$$ E_\rho[g]-\operatorname{KL}(\rho\|\Pi) =\frac12\log 3-\frac12\log\frac43 =\frac12\log\frac94 =\log\frac32 =\log E_\Pi[e^g]. $$

The posterior emphasizes the outcome with larger \(g\), but the divergence records the cost of that reweighting. Here the cost is exactly what makes the variational expression equal the log moment-generating function.

Using KL to Bound a Posterior Expectation

When the posterior is chosen for a practical reason, it need not be the exponential tilt of the function being bounded. The change-of-measure inequality still applies. It says that a posterior expectation can be large only if the prior exponential moment is large, the posterior departs sufficiently from the prior, or both.

Worked Example: A Posterior Expectation with a KL Penalty

Let \(\Pi=(1/4,3/4)\), \(\rho=(3/4,1/4)\), and \(g=(1,0)\). First calculate the divergence:

$$ \operatorname{KL}(\rho\|\Pi) =\frac34\log\frac{3/4}{1/4}+\frac14\log\frac{1/4}{3/4} =\frac34\log3-\frac14\log3 =\frac12\log3 \approx0.5493. $$

The posterior expectation is \(E_\rho[g]=(3/4)(1)+(1/4)(0)=0.75\). Under the prior,

$$ E_\Pi[e^g]=\frac14e+\frac34 \approx1.4296, \qquad \log E_\Pi[e^g]\approx0.3574. $$

The bound is therefore \(E_\rho[g]\leq0.5493+0.3574\approx0.9067\), which is valid since \(0.75\leq0.9067\). The posterior puts three times as much probability as the prior on the outcome where \(g=1\), and the positive KL term accounts for that shift.

The inequality is useful because it holds for every posterior with finite KL divergence, not just for a posterior selected by exponential tilting. In PAC-Bayesian arguments, it lets an average under a data-dependent posterior be related to an exponential moment under a reference prior. Further assumptions and probability arguments are needed to turn that deterministic relation into generalization bounds.

Common Mistake

A tempting but incorrect shortcut is to say that a posterior expectation is at most the prior expectation plus KL divergence. The theorem does not give \(E_\rho[g]\leq E_\Pi[g]+\operatorname{KL}(\rho\|\Pi)\). The term involving the prior is \(\log E_\Pi[e^g]\), not \(E_\Pi[g]\). Exponentiation makes this a different quantity, especially when \(g\) can take large values.

For instance, in the three-outcome example, \(E_\Pi[g]=2/3\), while \(\log E_\Pi[e^g]\approx0.9699\). The proven upper bound uses the latter. Replacing it with the prior mean would require a separate argument and is not justified by change of measure. A second frequent error is to reverse the KL arguments: the penalty here is \(\operatorname{KL}(\rho\|\Pi)\), because the posterior is being compared with the prior.

Key takeaway: For bounded measurable \(g\), every posterior \(\rho\) with finite KL divergence satisfies \(E_\rho[g]\leq\operatorname{KL}(\rho\|\Pi)+\log E_\Pi[e^g]\). The log moment-generating function and the KL cost together give the exact variational description of the largest penalized posterior expectation.

Check Your Understanding

Use the definitions and derivations above to answer the following.

  1. Why does \(\rho\not\ll\Pi\) imply that \(\operatorname{KL}(\rho\|\Pi)=+\infty\)?
  2. In the proof of nonnegativity, which Radon–Nikodym derivative is integrated, and why does its integral equal one?
  3. For a bounded measurable \(g\), write the density of the exponentially tilted measure \(\Pi_g\) and state when equality holds in the change-of-measure inequality.
  4. For \(\Pi=(1/4,3/4)\) and \(g=(\log 3,0)\), verify the two probabilities of the tilted measure by normalizing the unnormalized weights.
  5. Why can the prior mean \(E_\Pi[g]\) not be substituted for \(\log E_\Pi[e^g]\) in the change-of-measure inequality without additional justification?

Previous

Next

Back to Tutorials
Clinical Biostats