Randomized Predictions Versus Deterministic Averages

Two Ways to Use a Weighted Dictionary

Suppose a finite dictionary contains candidate predictors $f_1,\ldots,f_M$, and weights $w_1,\ldots,w_M$ are nonnegative and sum to one. There are two different ways to use these weights on a new observation. One is to draw an index at random and use that candidate. The other is to average the candidates’ prediction values and return the average. They have different outputs, but under a useful condition the deterministic average has no greater expected loss.

The condition concerns the loss as a function of the prediction, not just the fact that the weights are nonnegative. In particular, the average must be an admissible prediction, and the loss must be convex over the set containing the candidate predictions.

Definition: Let $Z=(X,Y)$ be a new observation, and let $f_j(X)$ be the prediction from candidate $j$. Given weights $w_j$, a randomized predictor draws an index $J$ with $P(J=j)=w_j$, independently of $Z$, and returns $f_J(X)$. Its risk is $R_{\mathrm{rand}}=\mathbb{E}[\ell(Y,f_J(X))]$. The deterministic averaged predictor returns $\bar f(X)=\sum_{j=1}^M w_j f_j(X)$; its risk is $R(\bar f)=\mathbb{E}[\ell(Y,\bar f(X))]$.

Here the weights and candidate predictors are treated as fixed. If they were obtained from training data, the same comparison applies conditional on that training data, provided the new observation and the random index are independent of it. Throughout, assume the predictors and loss are measurable and that the risks under discussion are finite. These conditions ensure the expectations are well defined without needing to interchange an infinite sum and an integral.

Risk of Random Selection

Random selection means that the prediction itself is random, even when the new observation is fixed. Its expected loss is a weighted average of the candidates’ risks. This is an exact identity and does not require convexity.

Result: For a finite dictionary and a random index $J$ independent of $Z$, with $P(J=j)=w_j$, $$ R_{\mathrm{rand}} =\sum_{j=1}^M w_j R(f_j), \qquad R(f_j)=\mathbb{E}[\ell(Y,f_j(X))]. $$

To verify the identity, first condition on the selected index. For each possible $j$, the expected loss over the new observation is $R(f_j)$. Taking the expectation over the finite-valued index gives

\mathbb{E}[\ell(Y,f_J(X))] =\sum_{j=1}^M P(J=j)\, \mathbb{E}[\ell(Y,f_j(X))] =\sum_{j=1}^M w_j R(f_j).

The finite sum makes the calculation direct. In particular, random selection does not mean averaging the predictions: it means averaging their risks after accounting for the randomness in which candidate is used.

Worked Example: Random Selection Under Squared Error

Suppose $Y=1$ with probability one, and two candidates predict $f_1(X)=0$ and $f_2(X)=2$. Give them equal weights, and use squared-error loss $\ell(y,a)=(y-a)^2$.

The risk of the first candidate is $(1-0)^2=1$, and the risk of the second is $(1-2)^2=1$. Thus the randomized risk is

R_{\mathrm{rand}}=\tfrac12(1)+\tfrac12(1)=1.

The deterministic averaged prediction is $\bar f(X)=\tfrac12(0)+\tfrac12(2)=1$, so its risk is $(1-1)^2=0$. The two procedures are not equivalent: one returns either 0 or 2, while the other always returns 1.

When the Average Is No Worse

Let the possible prediction values lie in a convex set $C$ in a vector space. Convexity of $C$ means that every weighted average of its elements with nonnegative weights summing to one also belongs to $C$. Suppose that, for every possible response $y$, the function $a\mapsto\ell(y,a)$ is convex on $C$. Then the average prediction is admissible, and the loss at that average is no greater than the weighted average of the losses.

Theorem: Let $f_1(X),\ldots,f_M(X)$ take values in a convex set $C$, and suppose $a\mapsto\ell(y,a)$ is convex on $C$ for every $y$. For fixed weights $w_j\geq 0$ with $\sum_{j=1}^M w_j=1$, assume the risks are finite. Then $$ R(\bar f)\leq \sum_{j=1}^M w_jR(f_j)=R_{\mathrm{rand}}. $$

For completeness, the finite convexity inequality used here follows by induction. For one prediction it is equality. Suppose it holds for $m-1$ predictions, and consider $m$ positive weights. Write $s=\sum_{j=1}^{m-1}w_j=1-w_m$, and define $b=\sum_{j=1}^{m-1}(w_j/s)f_j(X)$. The first $m-1$ normalized weights sum to one. By the induction hypothesis and then convexity,

\ell\!\left(y,\sum_{j=1}^m w_j f_j(X)\right) =\ell\!\left(y,sb+w_m f_m(X)\right) \leq s\ell(y,b)+w_m\ell(y,f_m(X)) \leq \sum_{j=1}^m w_j\ell(y,f_j(X)).

This proves the pointwise inequality for any finite number of predictions; zero weights can simply be omitted. Apply it with $y=Y$, then take expectations. Since the sum is finite and each risk is finite, expectation distributes over the sum. The randomized-risk identity above then yields the theorem. $\square$

Worked Example: Averaging Under Absolute Error

Let $Y=0$ with probability one, and let two equally weighted candidates predict $-2$ and $2$. Use absolute-error loss $\ell(y,a)=|y-a|$, which is convex in $a$.

Each candidate has risk $|0-(-2)|=2$ and $|0-2|=2$, so $R_{\mathrm{rand}}=\tfrac12(2)+\tfrac12(2)=2$. The averaged prediction is $\bar f(X)=\tfrac12(-2)+\tfrac12(2)=0$, with risk $|0-0|=0$. The average is admissible and its risk is no greater than the randomized risk, as the theorem guarantees.

Worked Example: Averaging Binary Probabilities Under Log Loss

Suppose the response is binary and the candidates predict probabilities $p_1=0.2$ and $p_2=0.8$ for response $Y=1$, with equal weights. The log loss for observing $Y=1$ at probability $p$ is $-\log p$. On $0<p<1$, this is convex because its second derivative is $1/p^2>0$.

The randomized risk is the average of the two losses:

R_{\mathrm{rand}} =\tfrac12(-\log 0.2)+\tfrac12(-\log 0.8) =-\tfrac12\log(0.16) =\log(2.5) \approx 0.9163.

The averaged probability is $\bar p=\tfrac12(0.2)+\tfrac12(0.8)=0.5$, which is a valid probability. Its log loss is $-\log(0.5)=\log 2\approx0.6931$. Thus the deterministic probability average has lower risk in this example.

What the Guarantee Does—and Does Not—Say

The guarantee is about expected loss for an individual prediction under the stated convexity and admissibility conditions. It does not say that averaging always helps under every loss, or that the deterministic average must be strictly better. For example, if all candidates give the same prediction, the two risks agree. Convexity gives a weak inequality; it does not by itself quantify how much risk is reduced.

A practical issue is whether the prediction values can actually be averaged. Real-valued regression predictions can be averaged within the real line. Probability vectors can be averaged within the probability simplex, the set of nonnegative vectors whose coordinates sum to one. But class labels are not probability vectors: averaging labels may produce a number that is not a valid class label. Replacing that number with a class by thresholding or rounding changes the prediction rule, and the convexity argument no longer applies automatically.

Worked Example: A Majority Label Can Be Worse

Consider two binary classifiers with weights $0.6$ and $0.4$. The first predicts class 0, the second predicts class 1, and the true class is 1 with probability one. Under zero-one loss, the randomized classifier has risk

R_{\mathrm{rand}}=0.6(1)+0.4(0)=0.6.

A majority-vote classifier returns class 0, so its risk is $1$. This does not contradict the theorem: the average of the labels is $0.6(0)+0.4(1)=0.4$, not a class label, and zero-one loss on hard class predictions does not provide the needed convex-loss comparison on the set of labels. A probability-averaging rule followed by a classification decision is a different procedure and needs its own risk analysis.

Common Mistake

Wrong reasoning: “The weights sum to one, so the averaged predictor must have risk equal to the weighted average of the candidate risks.” This confuses averaging predictions with averaging losses. In general, the loss of an average is not equal to the average loss. In the squared-error example, the randomized risk is 1 while the deterministic average has risk 0.

Correction: First check that the average prediction belongs to the allowed prediction set. Then check convexity of the loss as a function of that prediction for each fixed response. Under those conditions the loss at the average is at most the weighted average of losses, so taking expectations establishes the risk comparison. Without them, neither equality nor the no-worse guarantee follows just from the weights.

Key takeaway: Random selection has risk equal to the weighted average of candidate risks. A deterministic weighted average is guaranteed to do no worse when predictions lie in a convex admissible set and the loss is convex in the prediction.

Check Your Understanding

Use the definitions and conditions above to answer these questions.

Why does the identity for randomized risk not require convexity of the loss?
State the two convexity-related conditions needed to guarantee that the deterministic average has no greater risk.
For squared-error loss, two equally weighted predictions are 1 and 5, while the response is always 3. Calculate the randomized risk and the risk of the deterministic average.
Why does the convex-loss guarantee not automatically apply to a majority-vote classifier under zero-one loss?
If the candidate predictions are probability vectors, what must be true of their weighted average for it to be an admissible prediction?