Data-Dependent Priors Without Information Leakage

Why Prior Independence Matters

A PAC-Bayes bound permits the posterior to respond to the data: it can concentrate on predictors that perform well empirically, with the concentration paid for through a Kullback–Leibler complexity term. The prior has a different role. It is the reference distribution against which that data-driven concentration is measured. If the same sample chooses both the prior and the posterior, the comparison can conceal how much the data determined the predictor.

The issue is not that a prior must be scientifically uninformed. A prior may encode domain knowledge or be designed after examining genuinely separate data. The requirement is that it be fixed independently of the observations used in the bound, unless a different argument explicitly accounts for its data dependence.

Setup: Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $D$. Let $\Theta$ be a measurable predictor space, and let the measurable loss satisfy $0\leq \ell(\theta,z)\leq 1$. Define $R(\theta)=E_{Z\sim D}[\ell(\theta,Z)]$ and $\widehat R_n(\theta)=n^{-1}\sum_{i=1}^n\ell(\theta,Z_i)$. For a distribution $Q$ on predictors, write $R(Q)=E_{\theta\sim Q}[R(\theta)]$ and $\widehat R_n(Q)=E_{\theta\sim Q}[\widehat R_n(\theta)]$.

For $a,b\in[0,1]$, let $\operatorname{kl}(a\|b)=a\log(a/b)+(1-a)\log((1-a)/(1-b))$, with the usual continuous endpoint conventions. A standard PAC-Bayes-kl bound says that if $P$ is a fixed prior independent of $Z_1,\ldots,Z_n$, then, with probability at least $1-\delta$, simultaneously for every posterior $Q$,

\operatorname{kl}\!\left(\widehat R_n(Q)\middle\|R(Q)\right) \leq \frac{\operatorname{KL}(Q\|P)+\log(2\sqrt n/\delta)}{n}.

Here $\operatorname{KL}(Q\|P)$ is relative entropy, equal to $E_Q[\log(dQ/dP)]$ when $Q$ is absolutely continuous with respect to $P$, and infinite otherwise. The simultaneous statement is what allows $Q$ to be selected after seeing the sample. It does not allow $P$ to be selected from that same sample: the theorem's probability guarantee assumes the reference prior is fixed independently.

What Goes Wrong With a Sample-Dependent Prior

The danger is clearest when the prior is made to equal an empirical-risk minimizer. Then the posterior can equal that prior, giving zero relative entropy, even if the selected predictor has poor risk on new observations. The following construction makes this failure exact rather than merely possible in principle.

Worked Example: A Prior That Memorizes the Sample

Let $X$ be uniform on $[0,1]$, let $Y$ be an independent fair binary label, and use zero-one loss for predictors $f:[0,1]\to\{0,1\}$: $\ell(f,(x,y))=\mathbf 1\{f(x)\neq y\}$. Take $\Theta$ to be the measurable binary predictors. Given the sample, choose $f_S$ to match every observed label at its observed input and to equal zero elsewhere. Set the data-dependent prior and posterior to $P_S=Q_S=\delta_{f_S}$.

With probability one, the finitely many observed inputs have population probability zero. Thus $f_S(X)=0$ for a fresh $X$ with probability one, and the independent fair label gives $R(f_S)=1/2$. On the training sample, $f_S$ matches every label, so $\widehat R_n(f_S)=0$. Also, $\operatorname{KL}(Q_S\|P_S)=0$, since the two point masses are identical.

For $n=1000$ and $\delta=0.05$, the left side of the displayed PAC-Bayes-kl bound would be $\operatorname{kl}(0\|1/2)=\log 2\approx0.693147$. Its proposed right side would be

\frac{\log(2\sqrt{1000}/0.05)}{1000} = \frac{\log(40\sqrt{1000})}{1000} \approx \frac{7.142757}{1000} =0.007142757.

The inequality fails, and this construction produces the failure with probability one. There is no contradiction with the PAC-Bayes theorem: $P_S$ was selected using the analyzed sample, so the theorem's fixed-prior condition was violated.

This example also shows why it is not enough to say that a prior is “chosen before optimizing the posterior.” If both choices use the same observations, the prior can already encode their information. The relevant question is whether the prior is independent of the sample on which the risk is evaluated.

Valid Alternative 1: Use Independent Pilot Data

Suppose a pilot sample is used to design the prior, and a separate sample is reserved for the bound. Conditional on the pilot sample, the resulting prior is fixed. Independence then leaves the observations in the analysis sample distributed according to $D$, so the ordinary PAC-Bayes bound applies conditionally.

Theorem: Let $S_0$ be a pilot sample independent of an analysis sample $S_1=(Z_1,\ldots,Z_n)$ of independent observations from $D$. Suppose $P_{S_0}$ is a measurable prior-valued function of $S_0$. Under the bounded-loss setup above, with probability at least $1-\delta$ over both samples, every posterior $Q$, including one chosen using $S_0$ and $S_1$, satisfies $$ \operatorname{kl}\!\left(\widehat R_n(Q)\middle\|R(Q)\right) \leq \frac{\operatorname{KL}(Q\|P_{S_0})+\log(2\sqrt n/\delta)}{n}. $$

Proof. Fix a realized pilot sample $S_0=s_0$ for which the prior is defined. Independence implies that, conditional on $S_0=s_0$, the analysis observations remain independent with distribution $D$, and $P_{s_0}$ is fixed. The standard PAC-Bayes-kl bound therefore gives conditional probability at least $1-\delta$ that the inequality holds simultaneously for every $Q$. Integrating this conditional failure probability over $S_0$ gives an unconditional failure probability at most $\delta$. The simultaneous guarantee includes posteriors chosen using both samples. $\square$

Worked Example: A Pilot-Designed Prior

Suppose a pilot study is used to construct a prior that assigns probability $1/4$ to a candidate predictor $\theta^\star$. A separate analysis sample has $n=120$ observations. On that sample, the posterior is $Q=\delta_{\theta^\star}$, its empirical risk is $0.05$, and the prior probability of $\theta^\star$ is $1/4$. The two samples are independent.

The posterior is absolutely continuous with respect to the prior, and its relative entropy is $\operatorname{KL}(Q\|P)=\log(1/(1/4))=\log4\approx1.386294$. At confidence level $1-\delta=0.95$, the PAC-Bayes-kl bound gives

\operatorname{kl}(0.05\|R(\theta^\star)) \leq \frac{\log4+\log(2\sqrt{120}/0.05)}{120} = \frac{1.386294+6.082625}{120} \approx 0.06224.

The numerical bound controls the binary relative entropy between the observed risk and the true risk; it is not itself an additive risk error. Crucially, the prior probability $1/4$ can be used here because it was determined from data independent of these 120 observations.

Valid Alternative 2: Split the Sample

Sample splitting is a direct implementation of the same independence principle. Use one part of the data to choose a prior, design a predictor class, or tune a procedure. Use the other part only for the empirical risk in the PAC-Bayes bound. If the full sample has size $N$, and $m$ observations are reserved for evaluation, the complexity and confidence terms use $m$, not $N$.

Choose the split.
Partition the independent observations into a design sample and an evaluation sample of size $m$.

Design using the first part.
Construct $P$, and if desired choose a procedure for producing $Q$, using only the design sample.

Evaluate using the second part.
Apply the PAC-Bayes bound to the evaluation observations, using $m$ in its complexity and confidence terms.

Conditionally on the design sample, the evaluation observations remain independent from it and have distribution $D$. Thus the independent-pilot proof applies with the evaluation sample as $S_1$. If several splits or repeated evaluations are used and one reports whichever gives the best result, that selection also uses evaluation information; a guarantee must account for it, for example through a further independent evaluation sample or an appropriate multiplicity adjustment.

Worked Example: Accounting for the Evaluation Split

Take 240 independent observations. Use 120 to choose a prior, and reserve the remaining $m=120$ for evaluation. Suppose the selected predictor has evaluation empirical risk $0.05$, and its prior mass is $1/4$. With $\delta=0.05$, its KL complexity is $\log4$, and the evaluation-sample bound is

\operatorname{kl}(0.05\|R(\theta^\star)) \leq \frac{\log4+\log(2\sqrt{120}/0.05)}{120} = \frac{1.386294+6.082625}{120} \approx 0.06224.

The first 120 observations do not appear in this risk calculation or in the value of $m$; their role was to design the prior. Substituting $N=240$ into the denominator would incorrectly treat the design observations as if they had independently evaluated the selected predictor.

Valid Alternative 3: Put a Hyper-Prior on Candidate Priors

Sometimes it is useful to compare several prior distributions using the analyzed sample. A hyper-prior makes that choice part of the model rather than an uncharged data-dependent step. Let $h$ index a family of priors $P_h$ on $\Theta$, and let $\Pi$ be a fixed distribution on $h$, chosen independently of the sample. Use the joint prior $\Pi(dh)P_h(d\theta)$ on pairs $(h,\theta)$. A sample-dependent joint posterior $\rho(dh,d\theta)$ is then charged for moving both its hyperparameter distribution and its conditional predictor distribution away from this fixed joint prior.

Theorem: Assume the hyperparameter and predictor spaces are standard Borel spaces, the family $P_h$ is a measurable probability kernel, and the bounded-loss setup holds. For a fixed hyper-prior $\Pi$, with probability at least $1-\delta$, every joint posterior $\rho$ satisfies $$ \operatorname{kl}\!\left(\widehat R_n(\rho)\middle\|R(\rho)\right) \leq \frac{\operatorname{KL}\!\left(\rho\middle\|\Pi(dh)P_h(d\theta)\right)+\log(2\sqrt n/\delta)}{n}, $$ where $\widehat R_n(\rho)=E_{(h,\theta)\sim\rho}[\widehat R_n(\theta)]$, and $R(\rho)=E_{(h,\theta)\sim\rho}[R(\theta)]$.

Derivation. Regard each pair $(h,\theta)$ as one element of a predictor space, with loss $\ell((h,\theta),z)=\ell(\theta,z)$. The fixed distribution $\Pi(dh)P_h(d\theta)$ is a prior on this joint space and is independent of the observations. Applying the ordinary PAC-Bayes-kl bound on the joint space gives the displayed inequality. The hypotheses ensure the joint prior and loss are measurable, so the bound applies.

The complexity term has an informative decomposition. Write $\rho_H$ for the marginal distribution of $h$, and $\rho(d\theta\mid h)$ for a conditional distribution given $h$. When $\rho$ is absolutely continuous with respect to the joint prior, the Radon–Nikodym derivative factors into the marginal and conditional derivatives. Taking its logarithm and expectation under $\rho$ yields

\operatorname{KL}\!\left(\rho\middle\|\Pi(dh)P_h(d\theta)\right) = \operatorname{KL}(\rho_H\|\Pi) + E_{h\sim\rho_H}\!\left[\operatorname{KL}(\rho(\cdot\mid h)\|P_h)\right].

If absolute continuity fails, the joint relative entropy is infinite, so the bound is vacuous; the decomposition is understood in the extended-value sense. The first term pays for selecting or concentrating on hyperparameters. The second pays for concentrating on predictors relative to the corresponding candidate prior. Thus data may select among priors, but that selection is not free.

Worked Example: Paying for a Prior Choice

Consider two candidate priors, $P_1$ and $P_2$, with hyper-prior $\Pi(1)=\Pi(2)=1/2$. Suppose each assigns probability $1/4$ to its designated candidate predictor, $\theta_1$ or $\theta_2$. After observing the sample, the joint posterior selects $h=2$ and $\theta_2$ with probability one. Assume its empirical risk is $0.02$, and let $n=200$, $\delta=0.05$.

The joint posterior has mass one on $(2,\theta_2)$, where the joint prior has mass $(1/2)(1/4)=1/8$. Therefore its relative entropy is $\log8\approx2.079442$. The resulting bound is

\operatorname{kl}(0.02\|R(\theta_2)) \leq \frac{\log8+\log(2\sqrt{200}/0.05)}{200} = \frac{2.079442+6.338039}{200} \approx0.04209.

The complexity $\log8$ includes $\log2$ for selecting the second prior and $\log4$ for selecting its designated predictor. Using only the conditional cost $\log4$ would omit the data-driven choice between $P_1$ and $P_2$.

Common Mistake and Practical Guidance

Wrong reasoning: “The PAC-Bayes bound holds for every posterior, so it also holds if I use the data to choose the prior and set the posterior equal to it.” The simultaneous quantifier is over posteriors for a prior fixed independently of the sample. It does not make the result uniform over priors chosen after seeing the data. The memorization example shows that the missing independence condition can lead to a bound that is false with probability one.

Correction: Identify exactly which observations are used to define the prior and which observations appear in the empirical risk. If these are independent, condition on the prior-design data and use the evaluation sample size. If the same sample must select among candidate priors, place a fixed hyper-prior over them and include the resulting joint KL cost. In either case, record the data flow before applying the theorem; a prior that is “chosen first” in the analysis but computed from the analyzed observations is still data-dependent.

Key takeaway: Data-informed prior design is compatible with PAC-Bayes reasoning when independence is preserved by an auxiliary sample or a split, or when selection among priors is paid for through a fixed hyper-prior. Reusing the analyzed sample to choose a prior without such an adjustment invalidates the standard guarantee.

Check Your Understanding

Use the independence condition and the relevant complexity term to assess each setup.

A prior is fitted on an independent pilot sample, while the risk is evaluated on a fresh sample. Which sample size enters the PAC-Bayes bound, and why?
Why does a data-dependent prior equal to the posterior give zero KL complexity, and why does that not justify the ordinary bound?
A sample is split into 80 design observations and 40 evaluation observations. Which observations determine the prior, and what sample size is used in the bound?
In the hyper-prior example, what additional cost would be omitted by using only the KL divergence from the conditional predictor posterior to $P_h$?
Suppose several sample splits are tried and only the split with the strongest result is reported. Explain why the original single-split guarantee may no longer apply unchanged.