Convex Losses And Fixed Weighted Predictions

Why Convexity Controls Averaged Predictions

A finite dictionary offers several prediction rules for the same input. Instead of choosing one rule, we can average their predicted values using fixed nonnegative weights that sum to one. When the loss is convex as a function of the prediction, convexity gives a direct guarantee: the risk of that averaged prediction is at most the weighted average of the candidates’ risks.

The guarantee is pointwise before it is a statement about risk. For each possible observation, convexity compares the loss at the averaged prediction with the average of the losses at the candidate predictions. Taking expectations then gives the risk inequality. This distinction matters: the result concerns averaging predictions, not randomly choosing a candidate and not averaging labels.

Definition: Let $g_1,\ldots,g_M$ be prediction rules, with $g_j(x)$ taking values in a convex set $C$. A fixed weighted prediction is the rule $$ \bar g(x)=\sum_{j=1}^{M}\lambda_j g_j(x), $$ where the weights $\lambda_1,\ldots,\lambda_M$ are fixed numbers satisfying $\lambda_j\geq 0$ and $\sum_{j=1}^{M}\lambda_j=1$. The convexity of $C$ ensures that $\bar g(x)\in C$.

For an observation $Z=(X,Y)$ with distribution $P$, write the risk of a rule $g$ as $R(g)=E[\ell(Y,g(X))]$. Here $\ell(y,a)$ is the loss when the response is $y$ and the prediction is $a$. The condition needed is convexity in the prediction argument: for every fixed $y$, the function $a\mapsto\ell(y,a)$ is convex on $C$. The response $y$ is held fixed in this comparison.

Finite Jensen Inequality and the Risk Bound

A function $\phi$ on a convex set is convex if, for any $u,v$ in its domain and any $t\in[0,1]$, $\phi(tu+(1-t)v)\leq t\phi(u)+(1-t)\phi(v)$. The corresponding inequality for finitely many points is Jensen’s inequality.

Lemma (finite Jensen inequality): If $\phi$ is convex, $u_1,\ldots,u_M$ lie in its convex domain, and $\lambda_j\geq 0$ sum to one, then $$ \phi\!\left(\sum_{j=1}^{M}\lambda_j u_j\right) \leq \sum_{j=1}^{M}\lambda_j\phi(u_j). $$

For completeness, this finite form follows by induction on $M$. For $M=1$ it is equality, and for $M=2$ it is the definition of convexity. Suppose the result holds for $M-1$. If $\lambda_M=1$, the claimed inequality is equality. Otherwise set $s=\sum_{j=1}^{M-1}\lambda_j=1-\lambda_M>0$ and $v=\sum_{j=1}^{M-1}(\lambda_j/s)u_j$. Then $\sum_j\lambda_j u_j=sv+\lambda_Mu_M$. Convexity followed by the induction hypothesis gives $$ \phi\!\left(\sum_{j=1}^{M}\lambda_j u_j\right) \leq s\phi(v)+\lambda_M\phi(u_M) \leq \sum_{j=1}^{M-1}\lambda_j\phi(u_j)+\lambda_M\phi(u_M). $$ This proves the lemma. $\square$

Theorem (risk bound for a fixed weighted prediction): Suppose $g_1,\ldots,g_M$ are measurable prediction rules taking values in a convex set $C$. Suppose $\ell(y,a)$ is measurable and nonnegative, and is convex in $a\in C$ for every $y$. For fixed weights $\lambda_j\geq0$ summing to one, if $R(g_j)<\infty$ for every $j$ with $\lambda_j>0$, then $$ R(\bar g)\leq \sum_{j=1}^{M}\lambda_j R(g_j). $$

Proof. For each realized pair $(x,y)$, apply finite Jensen inequality to the convex function $a\mapsto\ell(y,a)$ and the values $g_1(x),\ldots,g_M(x)$: $$ \ell(y,\bar g(x)) =\ell\!\left(y,\sum_{j=1}^{M}\lambda_jg_j(x)\right) \leq \sum_{j=1}^{M}\lambda_j\ell(y,g_j(x)). $$ The right-hand side is measurable and has finite expectation, since it is a finite weighted sum of nonnegative losses with finite risks for all positively weighted candidates. The pointwise inequality therefore also ensures that the loss of $\bar g$ has finite expectation. Taking expectations and using linearity for the finite sum yields $$ R(\bar g)\leq E\!\left[\sum_{j=1}^{M}\lambda_j\ell(Y,g_j(X))\right] =\sum_{j=1}^{M}\lambda_jR(g_j). $$ $\square$

The weights are fixed for this statement: they do not change with the evaluated observation $(X,Y)$. The rules and weights may, for example, have been specified using an independent training sample. In that setting the same argument can be applied conditional on the training sample, provided the conditional rules and weights satisfy the stated assumptions and the risk is evaluated on an independent observation.

Worked Examples

Worked Example: Averaging Two Predictions Under Squared Loss

Let $Y$ equal 0 or 2 with probability $1/2$ each, and use squared loss $\ell(y,a)=(y-a)^2$. Consider the constant predictors $g_1=0$ and $g_2=2$, with weights $\lambda_1=\lambda_2=1/2$. Squared loss is convex in $a$, and the averaged prediction is $\bar g=1$.

The first candidate has risk $$ R(g_1)=\tfrac12(0-0)^2+\tfrac12(2-0)^2=0+2=2. $$ The second has risk $$ R(g_2)=\tfrac12(0-2)^2+\tfrac12(2-2)^2=2+0=2. $$ Thus their weighted average risk is $\tfrac12(2)+\tfrac12(2)=2$. The averaged predictor has risk $$ R(\bar g)=\tfrac12(0-1)^2+\tfrac12(2-1)^2=\tfrac12+\tfrac12=1. $$ So $1\leq2$, as the theorem guarantees. This example shows the bound can be strict.

Worked Example: A Nonquadratic Convex Loss

Let the response be constant at $Y=0$, and take $\ell(y,a)=\exp(a-y)$. For each fixed $y$, this loss is convex in $a$, since its second derivative with respect to $a$ is $\exp(a-y)>0$. Use constant predictions $g_1=0$, $g_2=2$, each with weight $1/2$. Their average is $\bar g=1$.

The risks are $R(g_1)=\exp(0)=1$ and $R(g_2)=\exp(2)=e^2$. The weighted candidate risk is therefore $$ \tfrac12(1)+\tfrac12e^2=\frac{1+e^2}{2}. $$ The averaged prediction has risk $R(\bar g)=\exp(1)=e$. Numerically, $e\approx2.7183$ and $e^2\approx7.3891$, so $R(\bar g)\approx2.7183$, while $(1+e^2)/2\approx4.1945$. Hence $e\leq(1+e^2)/2$, in agreement with convexity.

Worked Example: Convexity Need Not Be Strict

For a response $y\in\{-1,1\}$ and a real-valued score $a$, consider the hinge loss $\ell(y,a)=\max(0,1-ya)$. It is convex in $a$, as it is the maximum of two affine functions of $a$. Set $Y=1$, and use predictions $g_1=2$, $g_2=4$, with weights $1/2$ each.

Both candidate losses are zero: $\ell(1,2)=\max(0,-1)=0$ and $\ell(1,4)=\max(0,-3)=0$. The averaged score is $\bar g=3$, for which $\ell(1,3)=\max(0,-2)=0$. Thus the averaged risk and the weighted average risk are both zero, even though the candidate predictions differ. Convexity gives a non-strict inequality; it does not require a strict improvement.

When Is the Inequality Strict?

A useful strengthening applies when the loss is strictly convex in its prediction argument. Strict convexity means that for distinct $u,v\in C$ and $0<t<1$, the convexity inequality is strict. For a finite weighted average with at least two positive weights, finite Jensen inequality is strict whenever the corresponding predictions are not all equal.

Corollary: Suppose the theorem’s assumptions hold and, for every $y$, $a\mapsto\ell(y,a)$ is strictly convex. If at least two weights are positive and the positively weighted predictions $g_j(X)$ are not all equal with positive probability, then $$ R(\bar g)<\sum_{j=1}^{M}\lambda_jR(g_j). $$

To verify the strictness claim, define the pointwise gap $$ D=\sum_{j=1}^{M}\lambda_j\ell(Y,g_j(X))-\ell(Y,\bar g(X)). $$ Finite Jensen inequality gives $D\geq0$. Strict convexity gives $D>0$ whenever the positively weighted predictions are not all equal. By assumption this event has positive probability. A nonnegative random variable that is positive on an event of positive probability has positive expectation: indeed, $\{D>0\}=\bigcup_{k=1}^{\infty}\{D\geq1/k\}$, so at least one of these events has positive probability, and then $E[D]\geq P(D\geq1/k)/k>0$. The gap is integrable under the finite-risk assumptions, and $E[D]=\sum_j\lambda_jR(g_j)-R(\bar g)$. Therefore the risk inequality is strict. $\square$

What the Bound Does—and Does Not—Say

Because the weights sum to one, their weighted average of candidate risks is at least the smallest positively weighted candidate risk. The theorem says the averaged prediction has risk no greater than that weighted average. It does not say the averaged prediction must do better than the best candidate.

For example, let $Y=0$ with probability one, use squared loss, and average the constant predictions $g_1=0$ and $g_2=2$ with equal weights. Their risks are 0 and 4, so the best candidate has risk 0 and their weighted average risk is 2. The averaged prediction is 1 and has risk 1. The theorem’s conclusion $1\leq2$ holds, but the averaged prediction does not beat the best candidate’s risk of 0.

A frequent mistake is to reverse the inequality or to claim that averaging always improves on every candidate. The direction follows directly from convexity: loss at an average prediction is at most average loss. It is not a comparison with the minimum candidate loss. Another mistake is to apply the argument when the prediction set is not convex; the weighted average might then fail to be an admissible prediction. For instance, class labels themselves do not generally form a convex prediction space, although a real-valued score can.

The fixed-weight condition also matters. If weights are chosen using the same observation whose loss is being evaluated, they are no longer fixed in the pointwise argument as stated. A separate argument may be needed to account for that dependence. For weights chosen from independent training data, conditioning on that data makes the weights fixed for the independent evaluation observation, which is the setting in which the bound applies conditionally.

Key takeaway: If the prediction set is convex, the loss is convex in the prediction, and the weights are fixed and sum to one, then the risk of the weighted prediction is at most the weighted average of the candidate risks. This is a comparison to an average—not automatically to the best candidate.

Check Your Understanding

Use the assumptions and inequality from the tutorial to answer each question.

Why must the prediction set be convex for the weighted prediction to be a valid prediction?
State the convexity condition on $\ell(y,a)$ that is used in the pointwise part of the risk-bound proof.
If two candidates have risks 1 and 5 and receive weights $1/4$ and $3/4$, what upper bound does the theorem give for the averaged prediction’s risk?
Does strict convexity guarantee a strict risk inequality when the positively weighted predictions are equal almost surely? Explain.
Why is the theorem not, by itself, a guarantee that the weighted prediction beats the lowest-risk candidate?