A Bounded-Loss Oracle Inequality for Exponential Weights

Why Compare an Aggregate With the Best Candidate?

A finite dictionary offers several candidate predictors, but the best one in the population is unknown because its risk depends on the data-generating distribution. Exponential weights respond to the observed sample by assigning greater weight to candidates with smaller empirical loss. A useful guarantee asks whether the resulting aggregate has low risk relative to the best fixed dictionary member, without assuming that the member with the smallest observed loss is truly best.

For bounded losses, the comparison has two competing terms. A low temperature reduces the cost of a comparator's prior mass but makes the weights less responsive to the sample; a high temperature sharpens the weights but increases the bounded-loss penalty. The oracle inequality makes that tradeoff explicit.

Setting and Definitions

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$. A finite dictionary consists of predictors $f_1,\ldots,f_M$, fixed independently of these observations. Write $\ell_j(Z)=\ell(f_j,Z)$ for candidate $j$'s loss on one observation, and define its risk and empirical risk by

R_j=E[\ell_j(Z)], \qquad \widehat R_j=\frac{1}{n}\sum_{i=1}^n \ell_j(Z_i).

Assume throughout that the losses are measurable and $0\leq \ell_j(Z)\leq B$ almost surely for every candidate, where $0<B<\infty$. A prior is a probability vector $\pi=(\pi_1,\ldots,\pi_M)$ on the dictionary. We require $\pi_j>0$ for any candidate used as a comparator.

Definition: For a temperature $\eta>0$, the Gibbs weights based on the sample are $$ \widehat\rho_{\eta,j} = \frac{\pi_j\exp(-\eta n\widehat R_j)} {\sum_{k=1}^M\pi_k\exp(-\eta n\widehat R_k)}, \qquad j=1,\ldots,M. $$ These weights form a data-dependent probability distribution over the dictionary. The corresponding randomized prediction draws a candidate using $\widehat\rho_\eta$. If predictions can be averaged and the loss is convex in the prediction, the deterministic aggregate is the weighted average of the candidates.

The factor $n$ in the exponent matters: equivalently, the exponent is $-\eta$ times the sum of the observed losses. Thus $\eta$ is an inverse-loss-scale temperature for cumulative loss. The theorem below allows every positive $\eta$; it does not require an exp-concavity or mixability assumption.

Two Ingredients

For probability vectors $\rho$ and $\pi$, with $\rho_j=0$ whenever $\pi_j=0$, define the relative entropy $ \mathrm{KL}(\rho\Vert\pi)=\sum_j\rho_j\log(\rho_j/\pi_j) $, taking zero terms to be zero. The Gibbs weights minimize empirical risk plus a relative-entropy penalty.

Result: For any real numbers $a_1,\ldots,a_M$ and any probability vector $\pi$, $$ -\frac{1}{c}\log\left(\sum_{j=1}^M\pi_j e^{-ca_j}\right) = \min_{\rho}\left\{\sum_{j=1}^M\rho_j a_j+ \frac{\mathrm{KL}(\rho\Vert\pi)}{c}\right\}, \qquad c>0, $$ where the minimum is over probability vectors supported on the support of $\pi$. It is attained at $\rho_j\propto \pi_j e^{-ca_j}$.

To verify the identity, let $q_j=\pi_j e^{-ca_j}/\sum_k\pi_k e^{-ca_k}$. Direct substitution gives $\mathrm{KL}(\rho\Vert q)=\mathrm{KL}(\rho\Vert\pi)+c\sum_j\rho_j a_j+\log\sum_k\pi_k e^{-ca_k}$. Since relative entropy is nonnegative, the expression being minimized is at least the left side; equality holds at $\rho=q$. Taking $a_j=\widehat R_j$ and $c=\eta n$, and comparing the minimum with the choice placing all mass on candidate $j$, yields

\sum_k\widehat\rho_{\eta,k}\widehat R_k+ \frac{\mathrm{KL}(\widehat\rho_\eta\Vert\pi)}{\eta n} \leq \widehat R_j+\frac{\log(1/\pi_j)}{\eta n}.

The second ingredient controls the risk of any data-dependent distribution over candidates, including the Gibbs weights. For a probability vector $\rho$, write $R(\rho)=\sum_j\rho_jR_j$ and $\widehat R(\rho)=\sum_j\rho_j\widehat R_j$.

Result: For any measurable, sample-dependent probability vector $\rho$ supported on the support of $\pi$, and any $\lambda>0$, $$ E\left[R(\rho)-\widehat R(\rho)\right] \leq \frac{E[\mathrm{KL}(\rho\Vert\pi)]}{\lambda n} +\frac{\lambda B^2}{8}. $$

Here $R(\rho)$ is the population risk of the realized weights, not the risk of a fixed distribution chosen before seeing the sample. That distinction is why a uniform-in-the-posterior argument is needed.

Proof of the Expected-Risk Result

For each sample, the variational identity for relative entropy gives

\lambda n\{R(\rho)-\widehat R(\rho)\} -\mathrm{KL}(\rho\Vert\pi) \leq \log\left(\sum_{j=1}^M\pi_j e^{\lambda n(R_j-\widehat R_j)}\right).

For fixed $j$, $R_j-\widehat R_j$ is the average of $n$ independent, mean-zero variables $R_j-\ell_j(Z_i)$, each lying in an interval of length $B$. Hoeffding's lemma states that if a mean-zero random variable lies in an interval of length $B$, then its moment generating function at $t$ is at most $\exp(t^2B^2/8)$. Independence therefore gives

E\left[e^{\lambda n(R_j-\widehat R_j)}\right] \leq \exp\left(\frac{\lambda^2 nB^2}{8}\right).

Apply the concavity of the logarithm, then use the last bound term by term:

E\left[\log\left(\sum_j\pi_j e^{\lambda n(R_j-\widehat R_j)}\right)\right] \leq \log\left(\sum_j\pi_j E[e^{\lambda n(R_j-\widehat R_j)}]\right) \leq \frac{\lambda^2 nB^2}{8}.

Taking expectations in the variational inequality and dividing by $\lambda n$ proves the stated result. All sums are finite, and the bounded losses ensure the moment generating functions and expectations used here are finite. $\square$

The Bounded-Loss Oracle Inequality

Theorem: Under the setting and bounded-loss assumptions above, for every $\eta>0$ and every dictionary member $j$, $$ E\left[\sum_{k=1}^M\widehat\rho_{\eta,k}R_k\right] \leq R_j+\frac{\log(1/\pi_j)}{\eta n}+\frac{\eta B^2}{8}. $$ Consequently, the right side can be minimized over $j$. If the loss is convex in the prediction and the prediction space is convex, the same upper bound holds for the expected risk of the deterministic aggregate $\widehat f_\eta=\sum_k\widehat\rho_{\eta,k}f_k$.

To prove the randomized-prediction statement, apply the expected-risk result with $\rho=\widehat\rho_\eta$ and $\lambda=\eta$. Its left side is the expected Gibbs risk minus expected empirical Gibbs risk. Rearranging and then applying the Gibbs variational inequality gives

\begin{aligned} E\left[\sum_k\widehat\rho_{\eta,k}R_k\right] &\leq E\left[\sum_k\widehat\rho_{\eta,k}\widehat R_k +\frac{\mathrm{KL}(\widehat\rho_\eta\Vert\pi)}{\eta n}\right] +\frac{\eta B^2}{8}\\ &\leq E[\widehat R_j] +\frac{\log(1/\pi_j)}{\eta n} +\frac{\eta B^2}{8}\\ &=R_j+\frac{\log(1/\pi_j)}{\eta n} +\frac{\eta B^2}{8}. \end{aligned}

For the deterministic aggregate, convexity gives, pointwise in the observation and the sample, $\ell(\widehat f_\eta,Z)\leq\sum_k\widehat\rho_{\eta,k}\ell(f_k,Z)$. Integrating over a fresh $Z$ conditional on the sample, then taking expectation over the sample, bounds its expected risk by the randomized-prediction risk just proved. This establishes the claim. $\square$

Worked Examples

Worked Example: A Uniform Prior on Four Candidates

Suppose $B=1$, $n=100$, and the four candidates have equal prior probabilities. For a concrete risk comparison, let $Z$ take values $a$ and $b$, with $P(Z=a)=0.7$, and let the four losses on $(a,b)$ be $(0,1)$, $(1,0)$, $(0.5,0.5)$, and $(1,1)$. Their risks are $0.3$, $0.7$, $0.5$, and $1$, respectively, so the best dictionary risk is $0.3$.

For each candidate, $\pi_j=1/4$, and hence $\log(1/\pi_j)=\log 4$. Choosing the temperature that minimizes the two penalty terms gives $\eta=\sqrt{8\log(4)/(100\cdot1^2)}\approx0.3330$. The excess-risk penalty is

\frac{\log 4}{100\eta}+\frac{\eta}{8} = \sqrt{\frac{\log 4}{2(100)}} \approx 0.0832555.

Thus the expected risk of the Gibbs prediction is at most $0.3+0.0832555=0.3832555$. This is an upper bound, not a claim that the actual aggregate risk equals that number.

Worked Example: A Comparator With Small Prior Mass

Let $B=2$, $n=50$, and $\eta=0.2$. Consider three candidates with constant losses $0.30$, $0.20$, and $0.15$, so their risks are those same values. Use prior probabilities $(0.7,0.2,0.1)$. The third candidate is best, but its prior mass is only $0.1$.

Its prior-mass term is $\log(1/0.1)/(0.2\cdot50)=\log(10)/10\approx0.2302585$. The bounded-loss term is $0.2\cdot 2^2/8=0.1$. Therefore the theorem gives

E\left[\sum_k\widehat\rho_{\eta,k}R_k\right] \leq 0.15+0.2302585+0.1=0.4802585.

A small prior mass does not prevent comparison with that candidate, but it raises the price of doing so. The example also shows why one should distinguish the comparator's risk from the bound's additional complexity penalty.

Worked Example: Optimizing Temperature and Reading the Rate

For a fixed comparator $j$, write $A=\log(1/\pi_j)$. When $A>0$ and $B>0$, the penalty is $A/(\eta n)+\eta B^2/8$. Differentiating with respect to $\eta$ gives $-A/(n\eta^2)+B^2/8$, which is zero at $\eta_*=\sqrt{8A/(nB^2)}$. The second derivative $2A/(n\eta^3)$ is positive, so this is the minimizing temperature. Substitution yields

\frac{A}{\eta_* n}+\frac{\eta_*B^2}{8} = B\sqrt{\frac{A}{2n}}.

For example, with $A=\log 2$, $B=1$, and $n=20$, the optimized excess penalty is $\sqrt{\log(2)/40}\approx0.13164$, and $\eta_*=\sqrt{8\log(2)/20}\approx0.5266$. If the sample size is increased to $80$, the optimized penalty becomes $\sqrt{\log(2)/160}\approx0.06582$, exactly half as large. Doubling the loss range doubles the optimized penalty, while doubling the prior complexity $A$ multiplies it by $\sqrt{2}$.

How to Interpret the Bound

The inequality separates the oracle risk $R_j$ from the price for learning weights using the same data used to evaluate them. The prior-mass term is $\log(1/\pi_j)/(\eta n)$: more sample information, or greater prior mass on the comparator, reduces that part of the bound. The bounded-loss term is $\eta B^2/8$, linear in temperature and quadratic in the loss range. Balancing these terms gives an excess penalty of order $B\sqrt{\log(1/\pi_j)/n}$.

For a uniform prior on $M$ candidates, the prior-mass term uses $\log M$. A nonuniform prior instead permits a more favorable comparison for candidates assigned more mass. These statements concern an expected-risk comparison; they do not provide a high-probability guarantee, and boundedness alone does not imply a faster rate.

Common Pitfall

Calling the bounded-loss term quadratic in temperature. It is $\eta B^2/8$, so it is linear in $\eta$ and quadratic in $B$. It is the prior-mass term that decreases as $1/\eta$.
Dropping the prior-mass cost. The bound compares with a particular candidate, and the cost $\log(1/\pi_j)/(\eta n)$ reflects how much prior probability that candidate received.
Treating a randomized prediction and a deterministic average as identical for every loss. They have the same risk comparison when understood as randomized expected loss; convexity is needed to transfer the guarantee to a deterministic average prediction.

Key takeaway: For bounded losses, exponential weights achieve an expected-risk comparison with each fixed dictionary member. The comparator's prior mass controls complexity, while temperature balances that complexity cost against a penalty proportional to the squared loss range.

Check Your Understanding

Use the theorem and its assumptions to answer the following questions.

For a comparator with prior mass $\pi_j$, write the two excess-risk terms and state how each changes when $\eta$ increases.
If all losses lie in $[0,3]$, by what factor does the bounded-loss term change compared with losses in $[0,1]$, at the same temperature?
For a uniform prior on $M$ candidates, what does the comparator's prior-mass term become?
Why does the proof require the posterior inequality to hold for a sample-dependent distribution over candidates?
What additional condition allows the randomized-prediction guarantee to imply the same bound for a deterministic weighted average?