Nonuniform Priors and Relative-Entropy Complexity

Why Nonuniform Priors Change the Comparison

A finite dictionary need not treat all candidates as equally plausible or equally important. A predictor may receive more prior weight because it is simpler, was specified in advance, or represents a scientifically preferred model. Exponential weighting incorporates that preference directly: candidates with greater prior mass need less empirical evidence to retain weight, while candidates with small prior mass must perform better to compensate.

The key consequence is that a comparison need not charge every candidate the same $\log M$ complexity, where $M$ is the dictionary size. The natural charge for candidate $j$ is instead its negative log prior mass, $\log(1/\pi_j)$. This tutorial derives that statement from the prior-weighted entropy objective and distinguishes the resulting empirical inequality from a risk bound.

Definition: Let $f_1,\ldots,f_M$ be a finite dictionary of predictors, and let $\pi=(\pi_1,\ldots,\pi_M)$ be a prior distribution on its indices: $\pi_j>0$ and $\sum_{j=1}^M\pi_j=1$. For a probability vector $q$, define its relative entropy with respect to $\pi$ by $$ \operatorname{KL}(q\|\pi)=\sum_{j:q_j>0}q_j\log\!\left(\frac{q_j}{\pi_j}\right). $$ For fixed empirical losses $\widehat R_j$ and temperature $\eta>0$, the prior-weighted Gibbs distribution is $$ q_{\eta,j}=\frac{\pi_j\exp(-\eta\widehat R_j)}{\sum_{k=1}^M\pi_k\exp(-\eta\widehat R_k)}. $$

The prior must be positive on every candidate to which the comparison will apply. A candidate assigned zero prior mass is excluded from the Gibbs distribution and has infinite relative-entropy cost if a comparator puts positive mass on it. The uniform prior, $\pi_j=1/M$, recovers the familiar equal-weight construction.

Worked Examples: Weights and Prior Complexity

Worked Example: Computing Nonuniform Gibbs Weights

Suppose three candidates have prior probabilities $(0.5,0.3,0.2)$, empirical losses $(0,0.5,1)$, and $\eta=1$. Their unnormalized Gibbs weights are $$ 0.5e^0=0.5,\qquad 0.3e^{-0.5}\approx0.1819592,\qquad 0.2e^{-1}\approx0.0735759. $$ The normalizing constant is $$ Z=0.5+0.1819592+0.0735759=0.7555351. $$ Therefore $$ q_\eta\approx(0.5/0.7555351,\;0.1819592/0.7555351,\;0.0735759/0.7555351) =(0.6618,\;0.2408,\;0.0974). $$ The first candidate receives the largest weight because it has both the greatest prior mass and the smallest empirical loss.

Worked Example: Checking the Normalized Weights

For a direct numerical check, suppose the prior is $(0.4,0.35,0.25)$ and the unnormalized weights at $\eta=1$ are $(0.08120085,0.11035735,0.10000680)$. These correspond to losses $$ \widehat R_j=\log\!\left(\frac{\pi_j}{w_j}\right), $$ where $w_j$ is the unnormalized weight: indeed, $\pi_j e^{-\widehat R_j}=w_j$. The normalizing constant is $$ Z_1=0.08120085+0.11035735+0.10000680=0.29156500. $$ Dividing each weight by $Z_1$ gives $$ q_\eta\approx(0.2785,\;0.3785,\;0.3430). $$ For example, $0.29156500(0.3785)=0.11035735$ to the displayed precision, and $0.29156500(0.3430)=0.10000680$. The normalized entries sum to $1.0000$ after rounding.

Worked Example: The Cost of a Candidate’s Prior Mass

Let $\pi=(0.6,0.3,0.1)$ and $\eta=2$. The point-mass comparator on candidate $j$ has relative-entropy cost $$ \operatorname{KL}(\delta_j\|\pi)=\log(1/\pi_j). $$ The three costs are $\log(1/0.6)\approx0.5108$, $\log(1/0.3)\approx1.2040$, and $\log(1/0.1)\approx2.3026$. In the empirical comparison below, these costs are divided by $\eta$, giving penalties $0.2554$, $0.6020$, and $1.1513$.

Thus, at the same empirical loss, candidate 1 is charged less than candidate 3 because it received six times as much prior mass. Under a uniform prior on three candidates, each would instead receive the same charge $\log(3)/2\approx0.5493$.

The Variational Characterization

The prior-weighted Gibbs distribution is exactly the minimizer of empirical loss plus relative-entropy regularization. The following identity proves this and will also give the comparator inequality.

Theorem: Let $Z_\eta=\sum_{j=1}^M\pi_j e^{-\eta\widehat R_j}$, and let $q_\eta$ be the Gibbs distribution defined above. For every probability vector $q$, $$ \sum_{j=1}^M q_j\widehat R_j+\frac{1}{\eta}\operatorname{KL}(q\|\pi) = -\frac{1}{\eta}\log Z_\eta+\frac{1}{\eta}\operatorname{KL}(q\|q_\eta). $$ Consequently, $q_\eta$ minimizes the left-hand side over all probability vectors $q$.

Proof. Since $q_{\eta,j}=\pi_j e^{-\eta\widehat R_j}/Z_\eta$, taking logarithms gives $$ \log\!\left(\frac{q_j}{q_{\eta,j}}\right) =\log\!\left(\frac{q_j}{\pi_j}\right)+\eta\widehat R_j+\log Z_\eta $$ for each $j$ with $q_j>0$. Multiply by $q_j$ and sum. Because $\sum_jq_j=1$, $$ \operatorname{KL}(q\|q_\eta) =\operatorname{KL}(q\|\pi)+\eta\sum_jq_j\widehat R_j+\log Z_\eta. $$ Rearranging proves the identity. Relative entropy is nonnegative: using $\log x\le x-1$ for $x>0$, on the support of $q$, $$ -\operatorname{KL}(q\|q_\eta) =\sum_{j:q_j>0}q_j\log\!\left(\frac{q_{\eta,j}}{q_j}\right) \le \sum_{j:q_j>0}(q_{\eta,j}-q_j)\le 0. $$ Hence $\operatorname{KL}(q\|q_\eta)\ge0$, with equality when $q=q_\eta$. The identity therefore establishes the minimizing property. $\square$

Candidate-Specific Empirical and Oracle Comparisons

Taking $q=\delta_j$, the point mass on candidate $j$, makes the complexity term explicit. Since $\operatorname{KL}(\delta_j\|\pi)=\log(1/\pi_j)$, the minimizing property gives the following result.

Theorem: For every candidate $j$, $$ \sum_{k=1}^M q_{\eta,k}\widehat R_k \le \widehat R_j+\frac{\log(1/\pi_j)}{\eta}. $$ More generally, for every probability vector $q$, $$ \sum_{k=1}^M q_{\eta,k}\widehat R_k \le \sum_{k=1}^M q_k\widehat R_k+ \frac{\operatorname{KL}(q\|\pi)}{\eta}. $$

Proof. The variational characterization implies that the objective at $q_\eta$ is no larger than at any $q$. Thus $$ \sum_kq_{\eta,k}\widehat R_k+\frac{\operatorname{KL}(q_\eta\|\pi)}{\eta} \le \sum_kq_k\widehat R_k+\frac{\operatorname{KL}(q\|\pi)}{\eta}. $$ Because relative entropy is nonnegative, dropping the nonnegative term on the left preserves the inequality. This proves the general comparison. Substituting $q=\delta_j$ and evaluating its relative entropy gives the candidate-specific version. $\square$

The bound concerns the empirical loss averaged across candidates according to $q_\eta$. It is not, by itself, a statement that this empirical quantity equals population risk. A simple condition shows how the same comparison yields an oracle inequality for risk.

Corollary: Let $R_j$ denote the risk of candidate $j$, and define the risk of a randomized choice from the dictionary by $R(q)=\sum_kq_kR_k$. If, on an event under consideration, $|\widehat R_k-R_k|\le\varepsilon$ for every $k$, then for every candidate $j$, $$ R(q_\eta)\le R_j+\frac{\log(1/\pi_j)}{\eta}+2\varepsilon. $$

Proof. The uniform deviation condition gives $$ R(q_\eta)=\sum_kq_{\eta,k}R_k \le \sum_kq_{\eta,k}\widehat R_k+\varepsilon. $$ Apply the candidate-specific empirical comparison, then use $\widehat R_j\le R_j+\varepsilon$: $$ R(q_\eta)\le \widehat R_j+\frac{\log(1/\pi_j)}{\eta}+\varepsilon \le R_j+\frac{\log(1/\pi_j)}{\eta}+2\varepsilon. $$ This holds simultaneously for all $j$ on the stated event. $\square$

Worked Example: Reading an Oracle Bound

Suppose the uniform deviation condition holds with $\varepsilon=0.04$, $\eta=2$, and the three prior probabilities are $(0.6,0.3,0.1)$. If candidate 2 has risk $R_2=0.20$, the corollary gives $$ R(q_\eta)\le 0.20+\frac{\log(1/0.3)}{2}+2(0.04) =0.20+0.6020+0.08=0.8820. $$ If candidate 1 instead has risk $R_1=0.50$, its bound is $$ R(q_\eta)\le 0.50+\frac{\log(1/0.6)}{2}+0.08 =0.50+0.2554+0.08=0.8354. $$ The second bound is tighter even though candidate 1 has higher risk, because its prior mass is larger. The oracle comparison takes the smallest right-hand side over candidates; it balances fit against prior complexity rather than choosing by either quantity alone.

Why the Prior Can Replace a Dictionary-Size Penalty

With a uniform prior, $\log(1/\pi_j)=\log M$ for every candidate. The familiar dictionary-size penalty is therefore a special case of the more general prior-mass penalty. A nonuniform prior can make the comparison sharper for candidates assigned substantial mass, while imposing a larger charge on candidates assigned little mass.

This does not mean that a prior makes a difficult candidate free. Since $\sum_j\pi_j=1$, many candidates cannot all receive large prior mass. A small $\pi_j$ produces a large $\log(1/\pi_j)$, so the complexity term records how much prior weight the candidate was allocated. For a comparator distribution rather than a single candidate, the appropriate charge is $\operatorname{KL}(q\|\pi)$, which accounts for the whole distribution’s departure from the prior.

Common Pitfall

Using $\log M$ for every nonuniform prior. That is the uniform-prior special case, not the general result. For candidate $j$, compute $\log(1/\pi_j)$; for a distribution $q$, use $\operatorname{KL}(q\|\pi)$.
Calling the empirical comparison a population-risk guarantee without an assumption. The Gibbs inequality compares empirical losses. To obtain the displayed risk corollary, a deviation condition linking empirical losses to risks is needed.
Ignoring the support of the prior. A candidate with $\pi_j=0$ cannot be selected by these Gibbs weights, and a comparator assigning it positive mass has infinite relative entropy.
Forgetting the temperature factor. The complexity is divided by $\eta$. The prior determines the charge, while $\eta$ determines how strongly that charge enters the objective.

Key takeaway: Nonuniform Gibbs weights are proportional to prior mass times an exponential loss factor. Their variational comparison charges a candidate by $\log(1/\pi_j)/\eta$, or a comparator distribution by $\operatorname{KL}(q\|\pi)/\eta$. The $\log M$ penalty appears when, and because, the prior is uniform.

Check Your Understanding

Work through these questions using the definitions and results above.

For a prior $(0.5,0.3,0.2)$, calculate the relative-entropy cost of a point-mass comparator on each candidate.
Why does a uniform prior produce the same candidate penalty for every dictionary member?
State the variational identity that characterizes $q_\eta$, and identify the term that guarantees it is a minimizer.
If a candidate has prior probability $0.05$, what is its empirical complexity penalty when $\eta=2$?
What additional condition is used to turn the empirical comparison into the stated risk inequality?