Exp-Concavity and Mixability of Prediction Losses

Why These Two Properties Matter

An aggregation rule combines several candidate predictions into one. Convexity of a loss can make the loss of an averaged prediction no worse than the average loss of the candidates, but that comparison can leave a substantial gap. Exp-concavity and mixability describe stronger ways to control the loss of an aggregate. They are closely related, but they are not the same property: exp-concavity is a shape condition on the loss as a function of the prediction, while mixability asks directly whether a suitable aggregate can satisfy a particular loss bound.

Both properties depend on the scale of the loss and on the prediction domain. A loss may have one property on a restricted domain but not on a larger one. We therefore state the domain and the constant explicitly throughout.

The aggregate \(p_*\) in the definition of mixability must be chosen from the predictions and weights, not separately for each outcome \(y\). The same \(p_*\) must make the inequality hold for every possible outcome. Zero weights are allowed and contribute zero to the sum. Since \(\ell\) is real-valued and at least one weight is positive, the sum inside the logarithm is positive.

A Curvature Test for Exp-Concavity

When the loss is twice continuously differentiable in \(p\), exp-concavity has a local matrix test. The domain qualifications matter: the ordinary Hessian condition applies on the interior of a full-dimensional domain. If the domain lies in a lower-dimensional affine space, only directions within that space are relevant.

Proof. Fix \(y\) and write \(g(p)=\exp\{-\eta\ell(p,y)\}\). Differentiating by the chain rule gives

Because \(g(p)>0\) and \(\eta>0\), the Hessian \(\nabla_p^2g(p)\) is negative semidefinite exactly when the stated curvature inequality holds. A twice continuously differentiable function on an open convex set is concave if and only if its Hessian is negative semidefinite there. This gives the equivalence on \(\operatorname{int}(\mathcal D)\), which is convex.

For the boundary, if \(g\) is concave on \(\mathcal D\), its restriction to the interior is concave, so the Hessian condition holds there. Conversely, if that condition holds on the interior, \(g\) is concave there. For any \(p,q\in\mathcal D\), choose \(r\in\operatorname{int}(\mathcal D)\) and set \(p_\varepsilon=(1-\varepsilon)p+\varepsilon r\) and \(q_\varepsilon=(1-\varepsilon)q+\varepsilon r\), where \(0<\varepsilon<1\). Both points lie in the interior. Concavity there gives the concavity inequality for \(p_\varepsilon,q_\varepsilon\). Letting \(\varepsilon\) decrease to zero and using continuity of \(g\) gives that inequality for \(p,q\). Thus concavity extends to the boundary. Since \(y\) was arbitrary, the result holds for every outcome. \(\square\)

If \(\mathcal D\) has lower affine dimension, the same differentiation applies, but the Hessian inequality should be tested only in directions parallel to its affine hull. An ambient-space Hessian condition can impose restrictions in directions that no feasible prediction can move. That is why the full-dimensional hypothesis in the theorem cannot simply be omitted.

Exp-Concavity Provides a Mixability Aggregate

The relation between the two properties follows directly from Jensen's inequality. If the transformed loss is concave, its value at the weighted average prediction is at least the weighted average of its values at the candidates. Taking logarithms reverses the comparison because of the negative sign.

Proof. Convexity of \(\mathcal D\) ensures that \(p_*=\sum_i\alpha_i p_i\) belongs to \(\mathcal D\). Fix any \(y\in\mathcal Y\). By concavity of \(p\mapsto\exp\{-\eta\ell(p,y)\}\) and Jensen's inequality,

The two sides are positive. Taking logarithms preserves their order, and multiplying by \(-1/\eta\) reverses it. Therefore

This holds for every \(y\), using the same \(p_*\), so the definition of \(\eta\)-mixability is satisfied. \(\square\)

This implication is one-way in general. Mixability permits a suitable aggregate that need not be the arithmetic average. Consequently, a loss can be mixable even when its transformed loss is not concave and the curvature test fails.

What the Conditions Do—and Do Not—Say

The curvature criterion is useful because it turns a global concavity question into a pointwise inequality involving the gradient and Hessian of the loss. The right side, \(\eta\nabla_p\ell\nabla_p\ell^{\mathsf T}\), grows with the squared slope of the loss. A loss that bends upward strongly enough relative to its slope can satisfy the condition; a steep loss with little curvature may fail it. Boundedness alone does not guarantee exp-concavity: boundedness controls loss values, not the local derivatives required by the curvature test.

The constant also depends on the loss scale. If \(\tilde\ell=c\ell\) for \(c>0\), then \(\tilde\ell\) is \(\tilde\eta\)-exp-concave exactly when \(\ell\) is \(c\tilde\eta\)-exp-concave. A numerical value of \(\eta\) is therefore meaningful only together with the loss's units and scaling.

A common mistake is to identify the curvature inequality with the definition of mixability, or to conclude that failure of the inequality rules out mixability. The correction is to keep the roles distinct. The Hessian inequality characterizes exp-concavity under the stated smoothness and domain conditions. Jensen's inequality then proves that exp-concavity is sufficient for mixability. The linear-loss example shows why that implication cannot be reversed.

There is a second domain-related pitfall: applying a full ambient Hessian test to a prediction set with empty interior in \(\mathbb R^d\). Concavity on such a set constrains only changes that remain in its affine hull. For a lower-dimensional domain, use the Hessian quadratic form only along directions parallel to that affine hull, or reparameterize the predictions in coordinates on the affine hull.