Hierarchical Priors and Hyper-Posterior Bounds

Why Put a Prior on Models and Predictors?

A predictor may be chosen in two stages: first select a model or predictor class, then select a predictor within that class. A single flat prior over all predictors can represent this arrangement, but it can hide which part of the complexity comes from selecting a model and which comes from selecting a predictor inside it. A hierarchical prior keeps those costs visible.

The resulting guarantee controls the risk averaged over both stages of the posterior. Its central feature is that the divergence penalty has two parts: one for moving the model distribution away from its prior, and one for moving each within-model predictor distribution away from its own prior.

Hierarchical Prior and Posterior

Let \(m\) denote a model index, taking values in a measurable space \(\mathcal M\). For each \(m\), let \(\mathcal H_m\) be its predictor space. The loss \(\ell(h,z)\) is assumed measurable and bounded between 0 and 1. The data \(S=(Z_1,\ldots,Z_n)\) are independent and identically distributed from a distribution \(D\).

The prior \(\pi\) and the conditional priors \(P_m\) must be fixed independently of the sample for the result below. The posterior may depend on the sample. More generally, a prior constructed by a valid data-splitting or other information-control procedure can be used when its required independence conditions hold.

Why the Divergence Has Two Terms

The model-level cost is \(\operatorname{KL}(\rho\|\pi)\). The conditional cost is the average, under the selected model distribution, of \(\operatorname{KL}(Q_m\|P_m)\). Together they are exactly the divergence of the joint posterior from the joint prior.

To verify the identity, write \(r(m)=d\rho/d\pi(m)\) and \(q_m(h)=dQ_m/dP_m(h)\). The joint density ratio is \(dQ/d\Pi(m,h)=r(m)q_m(h)\). Integrating its logarithm under \(Q\) gives

The first expectation depends only on how much the posterior reweights models. The second measures the additional reweighting of predictors within each selected model. This decomposition is not an approximation: it is the joint KL divergence written in hierarchical form. If a posterior puts mass where the corresponding prior has none, absolute continuity fails and the associated divergence is infinite.

Proof of the Hierarchical Bound

The proof first controls an exponential moment under the joint prior, then transfers that control to every posterior using the KL divergence. For a fixed predictor \(h\), Hoeffding’s lemma applies because each loss lies in \([0,1]\). Independence of the observations therefore gives

Integrate this inequality with respect to the fixed joint prior \(\Pi\), and define \(Z(S)=\mathbb E_{(m,h)\sim\Pi}\exp\{\lambda\sum_i(R(h)-\ell(h,Z_i))\}\). Tonelli’s theorem applies to the nonnegative integrand, so \(\mathbb E_S Z(S)\leq\exp(n\lambda^2/8)\). Markov’s inequality then implies that, with probability at least \(1-\delta\),

Fix any posterior \(Q\) on this event. For \(Q\ll\Pi\), Jensen’s inequality yields

Indeed, writing \(q=dQ/d\Pi\), the left side is \(\mathbb E_Q[g]\), where \(g(m,h)=\lambda\sum_i(R(h)-\ell(h,Z_i))\). Jensen’s inequality gives \(\mathbb E_Q[g-\log q]\leq\log\mathbb E_Q[\exp(g)/q]=\log\mathbb E_\Pi[\exp(g)]\), which is the displayed inequality after adding \(\operatorname{KL}(Q\|\Pi)=\mathbb E_Q\log q\). Substituting the event bound for \(\log Z(S)\), dividing by \(\lambda n\), and applying the KL chain rule proves the theorem. The event depends on the prior and sample, not on \(Q\), so the conclusion holds simultaneously for all posteriors. \(\square\)

Worked Calculations

Common Pitfall and Practical Meaning

• Wrong: “The posterior selected a model, so the model-level KL is the complete complexity penalty.” This overlooks how much the posterior has changed the predictor distribution inside that model.
• Correction: Include \(\mathbb E_{m\sim\rho}\operatorname{KL}(Q_m\|P_m)\) as well as \(\operatorname{KL}(\rho\|\pi)\). If the posterior keeps \(Q_m=P_m\), the conditional cost is zero; otherwise it must be calculated.
• Wrong: “A convenient prior can be chosen after seeing the same sample without changing the argument.” The proof uses the prior before observing the sample. A data-dependent prior requires a valid independence or information-control justification.

The two-level form is useful when model classes have different structures or natural predictor priors. It allows the analysis to distinguish the price of selecting a class from the price of adapting within that class, while remaining exactly equivalent to a joint-prior PAC-Bayes bound. The temperature \(\lambda\) trades off the divergence penalty against the bounded-loss concentration term; it must be fixed for the stated guarantee unless a separate argument justifies data-dependent or simultaneous choices.