Problem-Solving Workshop on Loss-Specific Aggregation

Introduction

An aggregation problem is not solved just by writing down exponential weights. The guarantee depends on what is being averaged, how the loss behaves under that averaging, how the weights are updated, and which comparator is being used. A rule valid for a randomized choice among predictors need not justify using their average prediction.

This workshop organizes those decisions around four loss settings: bounded losses, squared loss, logistic loss on a bounded score range, and log loss. The central distinction is whether the loss supports a deterministic aggregate through exp-concavity, or whether the guarantee applies to the weighted average loss of a randomized predictor.

A Decision Rule for Choosing the Guarantee

Let there be \(M\) candidate predictors, with a prior \(\pi=(\pi_1,\ldots,\pi_M)\), where \(\pi_j>0\) and \(\sum_{j=1}^M\pi_j=1\). At round \(t\), candidate \(j\) makes prediction \(f_{t,j}\), and its loss after observing the outcome is \(\ell_{t,j}\). For a temperature \(\eta>0\), define the weights before round \(t\) by

A deterministic aggregate forms a prediction from these weights, often \(g_t=\sum_j w_{t,j}f_{t,j}\). A randomized aggregate instead draws candidate \(j\) with probability \(w_{t,j}\), so its conditional expected loss is \(\sum_jw_{t,j}\ell_{t,j}\). These are different procedures: the second equality defines expected loss for a randomized choice, not the loss of the averaged prediction.

The practical decision is therefore: use a deterministic aggregate when the loss is exp-concave on the full action range being used; use a bounded-loss regret guarantee for a randomized choice when only boundedness is available; and use the sequential probability mixture for log loss. The prior controls the cost of comparing with a candidate: a candidate with small prior mass has a larger penalty.

Two Guarantees and Their Assumptions

First, suppose each round’s loss is \(\eta\)-exp-concave in the prediction, the action set is convex, and the aggregate is \(g_t=\sum_jw_{t,j}f_{t,j}\). Let \(L_j=\sum_{t=1}^n\ell_{t,j}\) be candidate \(j\)’s cumulative loss. Then the deterministic aggregate satisfies

Here the candidates’ round-\(t\) losses are evaluated at their predictions for that round. The guarantee compares the aggregate with each fixed candidate, with a penalty determined by its prior mass.

To prove the result, set \(Z_t=\sum_j\pi_j\exp(-\eta\sum_{s<t}\ell_{s,j})\), so \(Z_1=1\). Exp-concavity and Jensen’s inequality give

Taking logarithms and summing over \(t\) yields \(-\eta\sum_t\ell(y_t,g_t)\geq\log Z_{n+1}-\log Z_1=\log Z_{n+1}\). Since \(Z_{n+1}\geq\pi_j e^{-\eta L_j}\), taking negative logarithms and dividing by \(\eta\) gives both inequalities. \(\square\)

If the loss is only known to lie in \([0,B]\), the deterministic prediction need not satisfy that result. For the randomized aggregate, however, exponential weights gives, for every \(\eta>0\),

For completeness, write \(m_t=\sum_jw_{t,j}\ell_{t,j}\). Hoeffding’s lemma for a finite random variable in \([0,B]\) gives \(\log\sum_jw_{t,j}e^{-\eta\ell_{t,j}}\leq-\eta m_t+\eta^2B^2/8\). The sum inside the logarithm is \(Z_{t+1}/Z_t\). Rearranging, summing over rounds, and using \(Z_1=1\) gives \(\sum_tm_t\leq-\log Z_{n+1}/\eta+\eta nB^2/8\). Finally \(Z_{n+1}\geq\pi_j e^{-\eta L_j}\) gives the stated bound. This proof uses bounded losses and randomized expected loss; it does not establish the same claim for an arbitrary deterministic average prediction. \(\square\)

If \(n\), \(B\), and the comparator’s prior mass are known, minimizing the last two terms gives \(\eta=\sqrt{8\log(1/\pi_j)/(nB^2)}\) and penalty \(B\sqrt{n\log(1/\pi_j)/2}\). This choice concerns the bounded-loss regret bound. When exp-concavity provides a deterministic guarantee, a valid exp-concavity temperature is the relevant constraint instead.

Worked Example: Bounded Loss and a Randomized Comparator

Squared Loss: Check the Action Range and the Arithmetic

For squared loss \(\ell(y,a)=(y-a)^2\), the deterministic guarantee requires a valid exp-concavity temperature on the action and outcome ranges. For \(y,a\in[0,1]\), differentiating twice with respect to \(a\) gives

Because \(|y-a|\leq1\), this is nonpositive whenever \(0<\eta\leq1/2\). Thus the required concavity holds throughout this range. If predictions or outcomes are not confined to the stated ranges, this argument no longer establishes that temperature.

Logistic Loss: Bounded Scores Give a Deterministic Rule

For a binary outcome \(y\in\{0,1\}\), let \(s\) be a score and use logistic loss \(\ell(y,s)=\log(1+\exp(-(2y-1)s))\). If \(s\in[-B,B]\), put \(z=(2y-1)s\). Differentiating with respect to \(s\), and writing \(r=1/(1+e^z)\), gives \(|\ell'(y,s)|=r\) and \(\ell''(y,s)=r(1-r)\). Hence \(\ell''/(\ell')^2=(1-r)/r=e^z\geq e^{-B}\). Since \[ \frac{d^2}{ds^2}e^{-\eta\ell(y,s)} =\eta e^{-\eta\ell(y,s)}\left(\eta(\ell'(y,s))^2-\ell''(y,s)\right), \] the transformed loss is concave whenever \(0<\eta\leq e^{-B}\). A weighted average of scores remains in \([-B,B]\), so the deterministic theorem applies to score averaging on this range.

Log Loss: Use the Sequential Probability Mixture

For log loss, candidate \(j\) assigns probability \(p_{t,j}(x_t)\) to the observed outcome \(x_t\). With weights proportional to \(\pi_j\) times the candidates’ likelihoods of past observations, predict using the mixture probability \(q_t(x)=\sum_j w_{t,j}p_{t,j}(x)\). Assume the candidate distributions are normalized and the mixture assigns positive probability to each observed outcome. Multiplying the sequential predictive probabilities gives the identity

To verify it, after \(t-1\) observations the weight of candidate \(j\) is proportional to \(\pi_j\prod_{s<t}p_{s,j}(x_s)\). The mixture probability at round \(t\) is the ratio of the weighted likelihood sum through \(t\) to the corresponding sum through \(t-1\). Multiplying these ratios cancels all intermediate sums, leaving the displayed identity; the initial sum is \(\sum_j\pi_j=1\). As the right side is at least \(\pi_j\prod_t p_{t,j}(x_t)\), taking negative logarithms proves

Common Mistakes and a Final Checklist

Most errors in loss-specific aggregation come from applying a valid formula to a different prediction rule, action range, or comparator. Before calculating, state what is being averaged and what the guarantee compares against.

• Using boundedness to justify deterministic averaging. Bounded losses give a regret bound for randomized expected loss. To transfer a bound to a deterministic average prediction, establish an appropriate property such as exp-concavity.
• Using an exp-concavity temperature outside its range. A temperature justified for squared loss on \([0,1]\), or logistic scores on \([-B,B]\), is not automatically valid beyond that range.
• Changing the comparator without changing the proof. The displayed exponential-weights bounds compare with a fixed candidate \(j\), and include \(\log(1/\pi_j)/\eta\) or \(\log(1/\pi_j)\). A different comparator requires a guarantee that covers it.
• Rounding intermediate quantities too early. Keep unrounded exponentials and logarithms through the final addition, then round the final result. This matters when reporting a cumulative loss or penalty.