Deriving Gibbs Weights from Entropy Penalization

Why Entropy Penalization Produces Weights

A finite dictionary offers several candidate predictors, each with an empirical risk computed on the observed sample. Selecting only the candidate with the smallest risk is one option; another is to assign a probability to every candidate and optimize over those distributions. An entropy penalty discourages a distribution from concentrating entirely on one candidate. The resulting optimization problem has a particularly simple solution: each candidate receives a weight proportional to an exponential of its negative empirical risk.

This tutorial derives that formula and establishes when it is the unique minimizer. The dictionary is finite, the empirical risks are finite real numbers, and the temperature parameter is strictly positive. The penalty uses the uniform distribution on the dictionary; replacing it with a nonuniform prior leads to a related but distinct formulation.

Objective Over the Simplex

Let \(f_1,\ldots,f_M\) be a finite predictor dictionary, where \(M\geq 1\). For a sample of size \(n\), write \(\widehat R_j\) for the empirical risk of predictor \(f_j\). Assume each \(\widehat R_j\) is a finite real number. A distribution over the dictionary is a vector \(q=(q_1,\ldots,q_M)\) in the probability simplex \( \Delta_M=\{q\in[0,1]^M:\sum_{j=1}^M q_j=1\} \).

Let \(u\) be the uniform distribution, with \(u_j=1/M\). For any \(q\in\Delta_M\), define its Kullback–Leibler divergence from \(u\) by \( \operatorname{KL}(q\|u)=\sum_{j=1}^M q_j\log(q_j/u_j) \), using the convention \(0\log 0=0\). For a temperature \(\tau>0\), the penalized objective is

The first term is the average empirical risk under the distribution \(q\). The second term penalizes departure from uniform weights, scaled by \(\tau\). Since \(u_j=1/M\), this divergence can also be written \( \operatorname{KL}(q\|u)=\sum_j q_j\log q_j+\log M \). The additive constant \(\log M\) matters for the objective's value, even though it does not change its minimizer.

The Variational Identity and the Minimizer

The formula follows from an exact identity, not an approximation. Because the dictionary is finite and every risk is finite, each term in the normalizing constant \( Z_\tau=\sum_k\exp(-\widehat R_k/\tau) \) is strictly positive and finite. Thus \(0<Z_\tau<\infty\), and every Gibbs weight \(q_j^\star\) is positive.

Proof. Since \(q_j^\star>0\), the divergence \(\operatorname{KL}(q\|q^\star)\) is defined for every \(q\in\Delta_M\), including distributions with zero coordinates. From the Gibbs formula, \( \log q_j^\star=-\widehat R_j/\tau-\log Z_\tau \). Therefore

Here the convention \(0\log 0=0\) justifies the expression when \(q_j=0\), and \(\sum_jq_j=1\) gives the final term. Adding \(\tau\log M-\tau\log Z_\tau\) to both sides yields exactly \(J_\tau(q)\), because \( \operatorname{KL}(q\|u)=\sum_jq_j\log q_j+\log M \).

For completeness, relative entropy is nonnegative, and it is zero only when its two distributions agree. In this case, that fact can be checked directly. For every coordinate with \(q_j>0\), the inequality \(\log x\leq x-1\) gives \(q_j\log(q_j^\star/q_j)\leq q_j^\star-q_j\). Summing over those coordinates and changing signs gives

Equality requires every positive coordinate to satisfy \(q_j=q_j^\star\), and it also requires no \(q_j^\star\) mass to lie outside the support of \(q\). Since all \(q_j^\star\) are positive, these conditions together hold only if \(q=q^\star\). The identity therefore shows that \(J_\tau(q)\) is minimized at \(q^\star\), with equality nowhere else. Substitution of \(q=q^\star\) gives the stated minimum value. \(\square\)

A Calculus Derivation

The same formula can be obtained by differentiating the objective. The variational identity has already established that the minimizer is interior: all its coordinates are positive. On the interior of the simplex, write \( J_\tau(q)=\sum_jq_j\widehat R_j+\tau\sum_jq_j\log q_j+\tau\log M \). To impose the constraint \(\sum_jq_j=1\), introduce a Lagrange multiplier \(\lambda\). The derivative with respect to \(q_j\) of the constrained expression is \( \widehat R_j+\tau(\log q_j+1)+\lambda \). At an interior stationary point, each such derivative is zero, so

The last two terms do not depend on \(j\). Exponentiating shows that \(q_j=C\exp(-\widehat R_j/\tau)\) for a common positive constant \(C\). Enforcing \(\sum_jq_j=1\) requires \(C=1/Z_\tau\). This recovers the Gibbs weights. The preceding theorem supplies the global optimality and uniqueness justification, so stationarity alone is not being used to claim a global minimum.

The curvature also explains why the solution is unique. In the interior, the Hessian of \(J_\tau\) is diagonal with entries \(\tau/q_j\). For any nonzero direction \(v\), \( v^\mathsf{T}\nabla^2J_\tau(q)v=\tau\sum_jv_j^2/q_j>0 \). In particular, this is positive for every nonzero direction tangent to the simplex, where \(\sum_jv_j=0\). Thus the objective is strictly convex in the interior. The variational identity additionally handles the boundary and confirms the unique minimizer over the entire closed simplex.

Risk Differences, Shifts, and the Zero-Temperature Boundary

The Gibbs formula depends on differences among risks rather than their common baseline. If every risk is increased by the same constant \(c\), then \( \exp(-(\widehat R_j+c)/\tau)=e^{-c/\tau}\exp(-\widehat R_j/\tau) \). The common factor \(e^{-c/\tau}\) appears in both numerator and normalizing constant and cancels. Hence the weights do not change. Likewise, the odds between any two candidates satisfy the exact relation

This follows by dividing the two normalized weights; the common \(Z_\tau\) cancels. These identities are useful checks on a calculation: equal risks must give equal weights, and adding a constant to every risk must preserve all weights.

The positivity condition \(\tau>0\) is essential to the theorem. At \(\tau=0\), the objective reduces to \(\sum_jq_j\widehat R_j\). Its minimizers are distributions supported on the candidates with smallest empirical risk. That minimizer is unique only when there is a single risk-minimizing candidate. For \(\tau>0\), by contrast, the KL penalty yields the unique Gibbs distribution even when several candidates tie.

Common Pitfall

A frequent error is to write \(q_j^\star=\exp(-\widehat R_j/\tau)\) and call these values probabilities. They are unnormalized positive numbers; in general, they do not sum to one. The required denominator is \( Z_\tau=\sum_k\exp(-\widehat R_k/\tau) \), and every coordinate must be divided by it. A second bookkeeping error is to replace \(\operatorname{KL}(q\|u)\) by \(\sum_jq_j\log q_j\) when reporting the objective value. These expressions differ by \(\log M\). They have the same minimizer because the difference is constant in \(q\), but they do not have the same minimum value.