Choosing Temperature from a Known Exp-Concavity Constant

Why Temperature Selection Needs a Guarantee

Exponential weights assigns greater weight to predictors with smaller accumulated loss. The temperature controls how sharply those weights respond: a larger temperature concentrates weight more aggressively. But choosing it only by intuition is risky. A temperature that is too small weakens the oracle bound, while one that exceeds what the loss geometry permits may invalidate the sharper guarantee altogether.

When the loss is exp-concave on the prediction domain, the temperature can be chosen using a known exp-concavity constant. The resulting finite-dictionary inequality is pathwise: it holds for every realized sequence of observations and does not require observations to be independent. A known loss range gives a different guarantee, valid without exp-concavity, which is useful as a benchmark.

Setup and Admissible Temperatures

At each time $t=1,\ldots,n$, a finite dictionary supplies predictions $f_1(x_t),\ldots,f_M(x_t)$. The outcome is $y_t$, and the loss of candidate $j$ is $\ell_{t,j}=L(y_t,f_j(x_t))$. A prior assigns masses $\pi_j>0$, with $\sum_{j=1}^M\pi_j=1$. The prior need not be uniform.

Definition: For a fixed outcome $y$, the loss $u\mapsto L(y,u)$ is $\alpha$-exp-concave on a convex prediction domain $\mathcal U$, for $\alpha>0$, if $u\mapsto \exp\{-\alpha L(y,u)\}$ is concave on $\mathcal U$. A known exp-concavity constant means that this condition has been verified for every outcome under consideration. A temperature $\lambda$ is admissible for the exp-concave guarantee when $0<\lambda\leq\alpha$.

The restriction to $\lambda\leq\alpha$ is valid because exp-concavity at $\alpha$ implies exp-concavity at every smaller positive value. In fact, write $g(u)=\exp\{-\alpha L(y,u)\}$. Then $\exp\{-\lambda L(y,u)\}=g(u)^{\lambda/\alpha}$. The power $z\mapsto z^{\lambda/\alpha}$ is concave and increasing on the nonnegative reals when $0<\lambda/\alpha\leq1$. Its composition with the nonnegative concave function $g$ is therefore concave.

For a temperature $\lambda>0$, define the weights just before observing $y_t$ by $p_{t,j}\propto \pi_j\exp\{-\lambda\sum_{s<t}\ell_{s,j}\}$. The aggregate prediction is $u_t=\sum_jp_{t,j}f_j(x_t)$, assumed to lie in $\mathcal U$. Write its loss as $\ell_t=L(y_t,u_t)$, and define the cumulative loss of dictionary element $j$ by $L_{n,j}=\sum_{t=1}^n\ell_{t,j}$.

Worked Example: Verifying a Temperature for Squared Loss

Take the loss $L(y,u)=(y-u)^2$, with $y=0$ and predictions $u\in[0,1]$. The exponential transform is $g(u)=\exp(-\alpha u^2)$. Its derivatives are $g'(u)=-2\alpha u\exp(-\alpha u^2)$ and $g''(u)=\exp(-\alpha u^2)(4\alpha^2u^2-2\alpha)$.

For $\alpha=1/2$, the second derivative becomes $g''(u)=\exp(-u^2)(u^2-1)$, which is nonpositive for every $u\in[0,1]$. Thus this loss is $1/2$-exp-concave on the stated domain when $y=0$. More generally the same calculation applies when $|y-u|\leq1$: replacing $u$ by the residual $r=y-u$, the second derivative with respect to $u$ has the same sign as $4\alpha^2r^2-2\alpha$, which is nonpositive for $\alpha=1/2$ and $|r|\leq1$. Any temperature up to $1/2$ is then admissible on that bounded-residual domain.

The Exp-Concave Oracle Inequality

Theorem: Suppose $\mathcal U$ is convex, each candidate prediction belongs to $\mathcal U$, and $u\mapsto L(y_t,u)$ is $\alpha$-exp-concave on $\mathcal U$ for every $t$. For exponential weights with any $0<\lambda\leq\alpha$, the aggregate predictions satisfy, for every $j\in\{1,\ldots,M\}$, $$ \sum_{t=1}^n \ell_t \leq L_{n,j}+\frac{\log(1/\pi_j)}{\lambda}. $$ Consequently, the right-hand side may be minimized over $j$.

This is a deterministic statement: once the outcomes and candidate predictions are fixed, the inequality holds without a probability qualification. The prior matters through the comparator's mass. A candidate given small prior mass pays a larger complexity term $\log(1/\pi_j)/\lambda$.

Proof. Define the unnormalized weight sum $Z_t=\sum_{j=1}^M\pi_j\exp\{-\lambda\sum_{s=1}^t\ell_{s,j}\}$, with $Z_0=1$. By exp-concavity at $\lambda$ and the concavity inequality for a finite weighted average, $$ \exp(-\lambda\ell_t) \geq \sum_{j=1}^M p_{t,j}\exp(-\lambda\ell_{t,j}). $$ The right-hand side equals $Z_t/Z_{t-1}$, since the weights $p_{t,j}$ are the normalized terms in $Z_{t-1}$. Taking logarithms, multiplying by $-1/\lambda$, and summing over $t$ gives $$ \sum_{t=1}^n\ell_t \leq -\frac{1}{\lambda}\sum_{t=1}^n\log\left(\frac{Z_t}{Z_{t-1}}\right) =-\frac{1}{\lambda}\log Z_n. $$ For any fixed $j$, $Z_n\geq\pi_j\exp(-\lambda L_{n,j})$. Hence $-\log Z_n/\lambda\leq L_{n,j}+\log(1/\pi_j)/\lambda$, proving the result. $\square$

The bound decreases as the admissible temperature increases. Therefore, if $\alpha$ is a valid known constant and there are no additional algorithmic constraints, the sharpest bound furnished by this theorem uses $\lambda=\alpha$. A smaller temperature is safe, but its complexity penalty is larger.

Worked Example: Selecting the Largest Admissible Temperature

Suppose $M=4$, the prior is uniform, the known exp-concavity constant is $\alpha=0.2$, and $n=1000$. For any one dictionary element, $\pi_j=1/4$, so its complexity is $\log(1/\pi_j)=\log 4\approx1.38629$. At $\lambda=0.2$, the cumulative excess-loss guarantee is $$ \frac{\log 4}{0.2} \approx 6.93147. $$ Dividing by $n=1000$, the average excess loss is at most approximately $0.00693147$.

If a conservative choice uses $\lambda=0.1$, the same calculation gives $1.38629/0.1\approx13.8629$ cumulative excess loss, or $0.0138629$ per observation. Halving the temperature doubles this theorem's complexity term. The conclusion concerns the guarantee; it does not assert that the realized loss itself must double.

What the Loss Range Adds

Exp-concavity gives a sharp guarantee only for admissible temperatures. Independently, a bounded loss range supplies a temperature-dependent bound that does not require exp-concavity. Suppose all candidate losses at every time lie in an interval of width $B$, meaning there is a common $a$ such that $a\leq\ell_{t,j}\leq a+B$. Suppose also that the loss is convex in its prediction, so the aggregate loss is at most the weighted average of candidate losses.

Result: Under these range and convexity assumptions, for every $\lambda>0$, $$ \sum_{t=1}^n \ell_t \leq L_{n,j}+\frac{\log(1/\pi_j)}{\lambda} +\frac{n\lambda B^2}{8} \qquad\text{for every }j. $$

Derivation. Convexity gives $\ell_t\leq\sum_jp_{t,j}\ell_{t,j}$. For a random variable supported on an interval of width $B$, Hoeffding's lemma states that $\log E[\exp\{s(X-E[X])\}]\leq s^2B^2/8$ for every real $s$. Apply it to the finite distribution putting mass $p_{t,j}$ on $\ell_{t,j}$, with $s=-\lambda$. Rearranging yields $$ \sum_jp_{t,j}\ell_{t,j} \leq -\frac{1}{\lambda}\log\left(\sum_jp_{t,j}e^{-\lambda\ell_{t,j}}\right) +\frac{\lambda B^2}{8}. $$ The logarithm term equals $-\log(Z_t/Z_{t-1})/\lambda$. Sum over time, telescope, and use $Z_n\geq\pi_j e^{-\lambda L_{n,j}}$, as in the theorem's proof. This proves the stated bound. $\square$

For a fixed comparator, let $C_j=\log(1/\pi_j)$. If $C_j>0$ and $B>0$, the range-based excess term $C_j/\lambda+n\lambda B^2/8$ is minimized over positive $\lambda$ at $\lambda_{\mathrm{range}}=\sqrt{8C_j/(nB^2)}$. Substitution gives the cumulative bound $\sqrt{C_jnB^2/2}$, or average excess $\sqrt{C_jB^2/(2n)}$. If $C_j=0$ and $B>0$, the term has infimum 0 as $\lambda\to0^+$, but no positive minimizer; if $B=0$ and $C_j>0$, its infimum is 0 as $\lambda\to\infty$, with no finite minimizer. If both are zero, the term is identically zero. This is a benchmark, not a replacement for checking exp-concavity: it trades off two terms and generally has a slower dependence on $n$ than the exp-concave guarantee.

Worked Example: Comparing the Range and Exp-Concave Bounds

Continue with $M=4$, a uniform prior, $n=1000$, and $B=1$. The range-optimal temperature is $$ \lambda_{\mathrm{range}} =\sqrt{\frac{8\log 4}{1000}} =\sqrt{0.0110904} \approx0.10531. $$ The two terms in the cumulative range bound are each approximately $13.164$, so their sum is approximately $26.328$. Equivalently, the optimized average bound is $\sqrt{\log(4)/2000}\approx0.02633$.

When the known exp-concavity constant is $\alpha=0.2$, choosing $\lambda=0.2$ instead gives the sharp average excess bound $6.93147/1000\approx0.00693147$. This is smaller than the range-based benchmark. The range calculation remains useful when no exp-concavity certificate is available; it should not be mistaken for a restriction requiring $\lambda\leq\lambda_{\mathrm{range}}$.

Worked Example: The Effect of a Nonuniform Prior

Suppose one candidate has prior mass $0.05$, the exp-concavity constant is $\alpha=0.4$, and the temperature is chosen at its admissible maximum. Its complexity is $\log(1/0.05)=\log 20\approx2.99573$. The cumulative excess term is $$ \frac{\log 20}{0.4} \approx \frac{2.99573}{0.4} \approx7.48933. $$ For $n=500$, this is an average excess term of $7.48933/500\approx0.0149787$.

If instead that candidate had prior mass $0.2$, with all other setup unchanged, its complexity would be $\log 5\approx1.60944$, and the cumulative term would be $\log 5/0.4\approx4.02359$. A favorable prior allocation improves the bound for that candidate; it does not change the loss sequence or guarantee that the candidate is best.

Practical Interpretation and a Common Pitfall

The loss range and the exp-concavity constant play different roles. The range $B$ controls the generic temperature tradeoff, while $\alpha$ certifies the curvature needed for the sharp inequality. They must be computed for the actual loss and prediction domain. If losses are rescaled by a positive factor $c$, their range scales by $c$, and a valid exp-concavity constant scales by $1/c$: indeed $\exp\{-(\alpha/c)(cL)\}=\exp(-\alpha L)$. The product of the loss scale and the corresponding temperature therefore remains consistent with the oracle bound.

Pitfall: choosing an arbitrarily large temperature. A larger temperature seems to shrink $\log(1/\pi_j)/\lambda$, but the exp-concave theorem only guarantees this bound for $\lambda\leq\alpha$. The correction is to use a verified constant and take $\lambda=\alpha$, or a smaller value if implementation considerations require it.
Pitfall: treating the range-optimal temperature as mandatory. The value $\sqrt{8C_j/(nB^2)}$ optimizes the generic bounded-loss expression. It is not an upper limit on temperature and need not be used when a sharper exp-concave guarantee applies.
Pitfall: using a constant established on the wrong domain. A loss may be exp-concave for bounded predictions but not on an unrestricted domain. Verify the domain and outcome conditions before selecting the temperature.

Key takeaway: With a verified $\alpha$-exp-concavity constant, every $0<\lambda\leq\alpha$ gives a finite-dictionary excess-loss term $\log(1/\pi_j)/\lambda$, so $\lambda=\alpha$ is optimal for that bound. A known loss range supplies a separate generic guarantee and a useful comparison, not a substitute for verifying exp-concavity.

Check Your Understanding

Use the definitions and inequalities above to answer the following.

Why does an $\alpha$-exp-concavity certificate also justify every temperature $0<\lambda<\alpha$?
For a comparator with prior mass $1/8$, what is its exp-concave complexity term at temperature $\lambda$?
Which assumption allows the aggregate prediction to remain in the domain $\mathcal U$, and where is convexity of the loss used in the range-based guarantee?
For the generic bounded-loss bound, derive the temperature minimizing $C_j/\lambda+n\lambda B^2/8$.
Explain why the range-optimal temperature is not an upper constraint on the temperature used with a verified exp-concavity constant.