Localized PAC-Bayes Bounds

Why Localize a PAC-Bayesian Bound?

A global PAC-Bayesian bound compares a posterior to a prior over the entire predictor class. But a learning problem may have a much smaller region of interest: predictors whose excess risk is small, or whose empirical losses are competitive. Focusing on that region can reduce the divergence term and can make variance-sensitive, fast-rate arguments more effective.

Localization is not automatic. Restricting to a set changes the reference prior, and choosing a set after seeing the data can invalidate a guarantee unless that selection is accounted for. The central questions are therefore: what set is being used, how was it chosen, and which divergence is measured?

Risk Sets and Conditioned Priors

Let $\mathcal H$ be a measurable predictor space, let $P$ be a probability prior on $\mathcal H$ independent of the sample, and let $Z_1,\ldots,Z_n$ be independent observations from a distribution $D$. Assume the loss $\ell(h,z)$ is jointly measurable and takes values in $[0,1]$. Write $R(h)=E_{Z\sim D}[\ell(h,Z)]$ and $\widehat R(h)=n^{-1}\sum_{i=1}^n\ell(h,Z_i)$. For a distribution $Q$ on predictors, write $R(Q)=E_{h\sim Q}R(h)$ and define $\widehat R(Q)$ in the same way.

Definition: Let $R^*=\inf_{h\in\mathcal H}R(h)$. The excess risk of $h$ is $r(h)=R(h)-R^*$. For $r\geq 0$, the risk-localized set is $A_r=\{h\in\mathcal H:r(h)\leq r\}$. For any fixed measurable set $A$ with $P(A)>0$, the conditioned prior is $P_A(B)=P(B\cap A)/P(A)$.

A distribution $Q$ supported on $A_r$ satisfies $R(Q)\leq R^*+r$, since $R(h)\leq R^*+r$ for every $h\in A_r$. The set $A_r$ is generally defined through the unknown population risk. It is useful for describing an oracle region, but cannot simply be identified from the sample and treated as fixed without further justification.

Worked Example: Conditioning a Finite Prior

Suppose $\mathcal H=\{h_1,\ldots,h_{10}\}$, $P$ is uniform, and $A=\{h_1,h_2\}$. Let $Q(h_1)=0.75$ and $Q(h_2)=0.25$. Then $P(A)=2/10=0.2$, and the conditioned prior assigns probability $1/2$ to each member of $A$.

The localized divergence is $ \operatorname{KL}(Q\|P_A)=0.75\log(1.5)+0.25\log(0.5)$. Numerically, this is $0.75(0.4055)+0.25(-0.6931)=0.1308$.

The global divergence is $ \operatorname{KL}(Q\|P)=0.75\log(7.5)+0.25\log(2.5)$, which is $0.75(2.0149)+0.25(0.9163)=1.7403$. The difference is $\log 5=1.6094$, the cost of the set's prior mass: $\log(1/P(A))$.

A Deviation Bound Within a Fixed Region

For bounded losses, a PAC-Bayes deviation inequality controls the difference between population and empirical Gibbs risks. The version below is convenient for localization because it can be applied with any fixed prior, including a prior conditioned on a fixed set.

Theorem: Let $P$ be a sample-independent prior on $\mathcal H$, and suppose the losses are measurable and in $[0,1]$. For any $0<\delta<1$, with probability at least $1-\delta$ over the sample, every probability distribution $Q$ on $\mathcal H$ satisfies $$ R(Q)-\widehat R(Q) \leq \sqrt{\frac{\operatorname{KL}(Q\|P)+\log(1/\delta)}{2n}}. $$ The inequality is understood to hold trivially when $\operatorname{KL}(Q\|P)=+\infty$.

Here is a derivation. For each fixed $h$, Hoeffding's lemma for independent variables in $[0,1]$ gives, for $\lambda>0$, $E[\exp\{\lambda(R(h)-\widehat R(h))\}]\leq\exp\{\lambda^2/(8n)\}$. Integrating with respect to $P$ and applying Markov's inequality shows that, with probability at least $1-\delta$, $$ \log E_{h\sim P}\exp\{\lambda(R(h)-\widehat R(h))\} \leq \frac{\lambda^2}{8n}+\log(1/\delta). $$ For any $Q$ absolutely continuous with respect to $P$, the change-of-measure inequality gives $\lambda E_Q[R-\widehat R]\leq \operatorname{KL}(Q\|P)+\log E_P e^{\lambda(R-\widehat R)}$. Combining these displays yields $$ R(Q)-\widehat R(Q) \leq \frac{\operatorname{KL}(Q\|P)+\log(1/\delta)}{\lambda} +\frac{\lambda}{8n}. $$ The event used above does not depend on $Q$, so the result holds simultaneously for all $Q$. Minimizing the right side over $\lambda>0$ gives the stated square-root bound. If the numerator is zero, take the limit as $\lambda$ decreases to zero. If $Q$ is not absolutely continuous with respect to $P$, its divergence is infinite and the assertion is vacuous. $\square$

Apply the theorem with $P_A$ in place of $P$. For a fixed measurable $A$ with $P(A)>0$, with probability at least $1-\delta$, every $Q$ supported on $A$ satisfies $$ R(Q)-\widehat R(Q) \leq \sqrt{\frac{\operatorname{KL}(Q\|P_A)+\log(1/\delta)}{2n}}. $$ This is a localized deviation guarantee: its complexity is measured relative to the prior restricted to the region, not relative to the full prior.

The identity explaining the change in complexity is exact. For $Q(A)=1$ and $Q\ll P$, the density of $P_A$ on $A$ is the density of $P$ divided by $P(A)$, so $$ \operatorname{KL}(Q\|P) =\int_A \log\!\left(\frac{dQ}{dP_A}\frac{1}{P(A)}\right)dQ =\operatorname{KL}(Q\|P_A)+\log\!\left(\frac{1}{P(A)}\right). $$ Thus conditioning removes the global penalty $\log(1/P(A))$ from the divergence, but the region must be fixed independently of the sample for the single-set guarantee just stated. If several candidate regions are considered, one can allocate confidence across them and use a union bound; the next example makes that cost explicit.

Worked Example: Comparing Localized and Global Deviations

Continue with the ten-predictor example, and suppose $n=1000$, $\delta=0.05$, and $Q$ is supported on $A$ with probabilities $0.75$ and $0.25$. The global deviation bound has numerator $1.7403+\log(20)=1.7403+2.9957=4.7360$. Its deviation radius is $\sqrt{4.7360/2000}=0.0487$.

Using the conditioned prior, the numerator is $0.1308+2.9957=3.1265$, giving radius $\sqrt{3.1265/2000}=0.0395$. The localized deviation radius is smaller because the posterior is much closer to the prior conditioned on $A$ than to the prior on all ten predictors.

If $A$ is instead selected from three fixed candidate sets $A_1,A_2,A_3$, a guarantee for all three can be obtained by applying the theorem to each with confidence level $\delta/3$, then taking a union bound. Each radius then uses $\log(3/\delta)=\log(60)=4.0943$, not $\log(20)$. For the same $Q$ and localized divergence, the radius becomes $\sqrt{(0.1308+4.0943)/2000}=0.0460$. This remains below the global radius here, but selection has reduced the advantage. The union bound is valid for fixed candidate sets; it does not justify searching unrestrictedly over sample-dependent sets.

Weighting Posterior Mass Toward Competitive Predictors

A hard restriction assigns zero posterior mass outside a chosen region. A softer alternative starts from a fixed reference prior $P_A$ and tilts it toward predictors with a small cost $c(h)$. The cost may be empirical risk or empirical excess loss. Since it may depend on the sample, the resulting distribution is a posterior; the reference prior remains sample-independent.

Definition: Let $c:\mathcal H\to\mathbb R$ be measurable and let $\tau>0$. If $Z_\tau=E_{h\sim P_A}[\exp\{-\tau c(h)\}]$ satisfies $0<Z_\tau<\infty$, define the tilted distribution $Q_\tau$ by $$ \frac{dQ_\tau}{dP_A}(h)=\frac{\exp\{-\tau c(h)\}}{Z_\tau}. $$

The requirement that the normalizing constant be finite matters: positivity alone does not ensure that the displayed density integrates to one. A convenient sufficient condition is that $c$ is bounded. More generally, the variational identity below is stated when $Z_\tau$ is finite and positive, $E_{Q_\tau}|c|<\infty$, and the divergences and expectations in the identity are well-defined and finite.

Under these conditions, the tilted distribution satisfies the Gibbs variational identity $$ E_{Q_\tau}[c]+\frac{1}{\tau}\operatorname{KL}(Q_\tau\|P_A) = \inf_{Q\ll P_A} \left\{E_Q[c]+\frac{1}{\tau}\operatorname{KL}(Q\|P_A)\right\} = -\frac{1}{\tau}\log Z_\tau, $$ where the infimum is over distributions for which the objective is well-defined. To verify it, for any such $Q$, use $\log(dQ_\tau/dP_A)=-\tau c-\log Z_\tau$ and expand: $$ \operatorname{KL}(Q\|Q_\tau) =\operatorname{KL}(Q\|P_A)+\tau E_Q[c]+\log Z_\tau. $$ Rearranging gives $E_Q[c]+\operatorname{KL}(Q\|P_A)/\tau =-\log Z_\tau/\tau+\operatorname{KL}(Q\|Q_\tau)/\tau$. The last divergence is nonnegative and equals zero at $Q=Q_\tau$, proving both the infimum and its attainment. $\square$

When $c=\widehat R$, the localized PAC-Bayes theorem can be applied to $Q_\tau$, even though it depends on the sample, because the theorem holds simultaneously for all posteriors. Its divergence is explicitly $\operatorname{KL}(Q_\tau\|P_A)=-\tau E_{Q_\tau}[\widehat R]-\log Z_\tau$. This formula makes the trade-off visible: increasing $\tau$ concentrates weight on low empirical risk, while the divergence term in the deviation guarantee can increase.

Worked Example: A Two-Predictor Gibbs Posterior

Let $A=\{h_1,h_2\}$, and let $P_A$ assign probability $1/2$ to each. Suppose the empirical costs are $c(h_1)=0.1$, $c(h_2)=0.4$, and $\tau=5$. Then $$ Z_5=\tfrac12 e^{-0.5}+\tfrac12 e^{-2} =0.303265+0.067668=0.370933. $$

The tilted probabilities are $Q_5(h_1)=0.303265/0.370933=0.8176$ and $Q_5(h_2)=0.067668/0.370933=0.1824$, to four decimal places. The expected cost is $E_{Q_5}[c]=0.8176(0.1)+0.1824(0.4)=0.1547$.

Using the exact tilted probabilities, its divergence is approximately $0.2181$. The objective is approximately $0.19835$. On the other hand, $-\log(0.370933)/5\approx0.19835$, confirming the variational identity. The posterior has moved most, but not all, of its mass to the predictor with lower empirical cost.

When Localization Sharpens a Guarantee

Localization can help in two related ways. First, if a posterior is concentrated on a region whose conditioned prior matches it well, its localized divergence can be substantially smaller. Second, risk-localized arguments can exploit additional structure: under suitable Bernstein conditions, the variance of excess loss is controlled by excess risk, so a localized analysis can lead to fast-rate behavior rather than the generic square-root deviation scale. The latter improvement requires the stated variance and tail hypotheses; simply restricting a posterior does not prove a fast rate.

The risk set $A_r$ describes predictors with $r(h)\leq r$, but it may be unknown. An empirical-cost tilt is implementable from data, yet it is not automatically a prior conditioned on a low-population-risk set. Its validity comes from applying the simultaneous PAC-Bayes event to a posterior chosen after observing the data. Any data-dependent choice of the reference prior or of a region used as if fixed requires a separate argument.

Common Pitfalls

Assuming positive normalization is enough. A normalizing constant must satisfy $0<Z_\tau<\infty$. If it is infinite, the proposed tilted density does not define a probability distribution.
Ignoring the choice of region. The fixed-set theorem applies to a set chosen independently of the sample. Searching over regions and reporting the best one requires confidence allocation or another valid selection argument.
Comparing divergences without changing the prior. For a posterior supported on $A$, the global divergence equals the localized divergence plus $\log(1/P(A))$. The two quantities use different reference distributions.
Claiming a fast rate from restriction alone. A smaller localized divergence can improve a bound, but a fast rate also needs appropriate assumptions, such as a Bernstein condition.

Key takeaway: Localization replaces a global comparison with one tailored to a predictor region or a tilted posterior. Track the reference prior, verify that the tilt is normalizable, and account for any data-dependent choice before interpreting the resulting guarantee.

Check Your Understanding

Use the definitions and derivations above to answer the following.

For a posterior supported on $A$, how does $\operatorname{KL}(Q\|P)$ relate to $\operatorname{KL}(Q\|P_A)$ and $P(A)$?
Why does a fixed-set PAC-Bayes bound not automatically justify choosing $A$ after inspecting the sample?
What condition on $Z_\tau$ is required for the Gibbs-weighted posterior to be a probability distribution?
In the two-predictor example, what happens to the mass on $h_1$ as $\tau$ increases? What trade-off can that create in a deviation bound?
Why does a localized posterior by itself not establish a fast rate?

What You'll Learn