Convex Hull Oracles and Comparator Risks

Two Different Risk Comparators

A finite collection of candidate predictors gives two natural standards for evaluating a learning procedure. The first asks how well it could do by choosing one candidate. The second asks how well it could do by combining candidates with fixed nonnegative weights. These are different population benchmarks: a mixture can improve on every individual predictor, but the improvement is not guaranteed to be strict.

The distinction matters whenever a risk bound or a performance claim names its comparator. A bound relative to the best candidate answers a selection question. A bound relative to the best convex mixture answers a richer aggregation question. The second benchmark is at least as demanding, because it optimizes over a set that includes every candidate.

Dictionary, Convex Hull, and Population Risk

Let \((X,Y)\) have a fixed population distribution. A predictor is a measurable function \(f\) that maps an input \(X\) to a scalar prediction. Let \(f_1,\ldots,f_M\) be a finite dictionary of predictors, where \(M\geq 1\). For a loss function \(\ell(y,a)\), the population risk of \(f\) is the expected loss on a new draw from this distribution.

Definition: The simplex of weights on a dictionary of size \(M\) is \(\Delta_M=\{w\in\mathbb{R}^M:w_j\geq 0,\ \sum_{j=1}^M w_j=1\}\). The convex hull of the dictionary is the collection of predictors \(f_w(x)=\sum_{j=1}^M w_j f_j(x)\), for \(w\in\Delta_M\). The population risk is \(R(f)=E[\ell(Y,f(X))]\), when this expectation is well-defined.

The weights in this definition are fixed across inputs: the same \(w\) is used at every \(x\). Thus the convex hull consists of global mixtures, not rules that choose a different weight vector for each input. A mixture predictor first averages the candidate predictions and then incurs the loss of that average.

Definition: The best-single-predictor oracle risk and the convex-hull oracle risk are, respectively, \(R_{\mathrm{dict}}^*=\min_{1\leq j\leq M}R(f_j)\) and \(R_{\mathrm{hull}}^*=\inf_{w\in\Delta_M}R(f_w)\). The first comparator chooses one dictionary member; the second chooses the best predictor in its convex hull.

The minimum in \(R_{\mathrm{dict}}^*\) exists because the dictionary is finite and its risks are assumed finite. The hull oracle is written as an infimum because an optimizing weight vector needs conditions that guarantee attainment. For example, if \(\ell(y,a)\) is continuous in \(a\) and there is an integrable random variable \(H(X,Y)\) such that \(|\ell(Y,f_w(X))|\leq H(X,Y)\) for every \(w\in\Delta_M\), then \(R(f_w)\) is continuous in \(w\). Indeed, for any sequence \(w^{(k)}\to w\), the predictions converge pointwise, the losses converge by continuity, and dominated convergence gives \(R(f_{w^{(k)}})\to R(f_w)\). Since \(\Delta_M\) is compact, a continuous risk function attains its minimum there.

How the Two Oracle Risks Compare

Each dictionary member is itself a convex-hull predictor: choose a weight vector with weight one on that member and zero elsewhere. Therefore, even without convexity of the loss, the hull oracle cannot have larger risk than the best-single-predictor oracle.

Theorem: If the risks of all dictionary members are finite, then \(R_{\mathrm{hull}}^*\leq R_{\mathrm{dict}}^*\). If, in addition, \(a\mapsto\ell(y,a)\) is convex for every \(y\) and the risks are finite, then for every \(w\in\Delta_M\), \(R(f_w)\leq\sum_{j=1}^M w_jR(f_j)\). Consequently, the mixture's risk is no greater than the corresponding weighted average of candidate risks.

Proof. For each \(j\), the weight vector that puts all its mass on \(f_j\) gives \(f_w=f_j\). Thus the convex hull contains the dictionary, and taking an infimum over the larger set proves \(R_{\mathrm{hull}}^*\leq R_{\mathrm{dict}}^*\). For the second claim, convexity gives, for each realized \((X,Y)\), \(\ell(Y,\sum_jw_jf_j(X))\leq\sum_jw_j\ell(Y,f_j(X))\). Taking expectations and using finiteness yields \(R(f_w)\leq\sum_jw_jR(f_j)\). \(\square\)

The inclusion argument does not require a convex loss. Convexity gives the additional weighted-risk inequality, but it does not by itself guarantee that a mixture strictly improves on the best candidate. The optimizer may lie at a vertex of the simplex, in which case the best hull predictor is a single dictionary member.

Worked Example: Squared-Error Regression With Constant Predictors

Suppose \(Y\) equals 0 or 2 with probability \(1/2\) each, and the input is irrelevant. Use squared loss \(\ell(y,a)=(y-a)^2\) and the dictionary of constant predictors \(f_1(x)=0\) and \(f_2(x)=2\). The population mean of \(Y\) is \(E[Y]=(0+2)/2=1\).

For \(f_1\), the risk is \(R(f_1)=\{(0-0)^2+(2-0)^2\}/2=2\). For \(f_2\), it is \(R(f_2)=\{(0-2)^2+(2-2)^2\}/2=2\). Hence \(R_{\mathrm{dict}}^*=2\).

A mixture with weight \(w\) on \(f_2\) predicts the constant \(2w\), where \(0\leq w\leq1\). Its risk is \(R(f_w)=\{(0-2w)^2+(2-2w)^2\}/2=4w^2-4w+2=1+4(w-\tfrac12)^2\). This is minimized at \(w=1/2\), with risk 1. Therefore \(R_{\mathrm{hull}}^*=1<2=R_{\mathrm{dict}}^*\). The mixture improves because it predicts the population mean, which neither dictionary member does.

Convex Mixtures Use One Weight Vector

A convex-hull predictor is not allowed to choose a different dictionary member separately at each input. This restriction is part of the comparator's definition, not a technical detail. The next example shows that the best global mixture can differ from a hypothetical input-by-input choice.

Worked Example: A Global Mixture Across Two Inputs

Let \(X\) take values \(a\) and \(b\) with probability \(1/2\) each, and let \(Y=0\) always. Under squared loss, define two predictors by \(f_1(a)=0,\ f_1(b)=2\) and \(f_2(a)=2,\ f_2(b)=0\).

For \(f_1\), the squared errors at \(a,b\) are \(0,4\), so \(R(f_1)=(0+4)/2=2\). For \(f_2\), they are \(4,0\), so \(R(f_2)=(4+0)/2=2\). Thus \(R_{\mathrm{dict}}^*=2\).

Let \(w\) be the weight on \(f_1\), so the weight on \(f_2\) is \(1-w\). The mixture predicts \(2(1-w)\) at \(a\) and \(2w\) at \(b\). Therefore \(R(f_w)=\{[2(1-w)]^2+(2w)^2\}/2=2[(1-w)^2+w^2]\). Completing the square gives \(R(f_w)=1+4(w-\tfrac12)^2\), so the global hull oracle has risk 1 at \(w=1/2\).

An input-dependent rule could choose \(f_1\) at \(a\) and \(f_2\) at \(b\), giving zero risk, but that rule is not a single convex combination with common weights. It is outside the convex hull defined here. The hull oracle is therefore a specific, restricted comparator.

Probability Predictors and a Second Risk Calculation

The same comparison applies when predictors output probabilities. For a binary outcome, a probability predictor takes values in \([0,1]\). Under Brier loss, the loss is the squared difference between the outcome and the predicted probability. Convex mixtures of probability predictions remain valid probabilities because a weighted average of numbers in \([0,1]\) also lies in \([0,1]\).

Worked Example: Brier Risk for Two Constant Probabilities

Suppose \(Y\sim\operatorname{Bernoulli}(0.3)\), and consider constant probability predictions \(p_1=0.1\) and \(p_2=0.7\). The Brier loss is \((Y-p)^2\). For any constant \(p\), expanding around \(q=E[Y]=0.3\) gives \(E[(Y-p)^2]=\operatorname{Var}(Y)+(p-q)^2=0.3(0.7)+(p-0.3)^2\).

For \(p_1=0.1\), the risk is \(0.21+(-0.2)^2=0.25\). For \(p_2=0.7\), it is \(0.21+(0.4)^2=0.37\). Thus \(R_{\mathrm{dict}}^*=0.25\). The mixture \(p_w=wp_1+(1-w)p_2\) can attain \(0.3\): solving \(0.1w+0.7(1-w)=0.3\) gives \(w=2/3\). Its risk is \(0.21+(0.3-0.3)^2=0.21\). Since the variance term \(0.21\) is unavoidable and the squared bias is nonnegative, this is the hull-oracle risk. Hence \(R_{\mathrm{hull}}^*=0.21<0.25=R_{\mathrm{dict}}^*\).

Reading Comparator Claims Correctly

A statement that compares a procedure with \(R_{\mathrm{dict}}^*\) permits the procedure to be judged against the best available single candidate. Comparing with \(R_{\mathrm{hull}}^*\) asks for performance relative to the best fixed convex combination. Because \(R_{\mathrm{hull}}^*\leq R_{\mathrm{dict}}^*\), a guarantee relative to the hull oracle can be more informative, but it is also a different and generally stronger comparison.

A common mistake is to treat the two oracle risks as interchangeable because both are defined using the same finite dictionary. They are not: the first optimizes over \(M\) candidates, while the second optimizes over all weight vectors in \(\Delta_M\). Another mistake is to assume convexity forces a strict improvement. The proved inequality only says that each mixture's risk is no greater than its weighted average candidate risk; the best mixture may still be a single candidate.

Key takeaway: Name the comparator explicitly. The best-single-predictor oracle selects one \(f_j\); the convex-hull oracle selects a fixed weight vector and predicts \(\sum_jw_jf_j(x)\). Hull risk is never worse than dictionary risk, and convex losses also give a risk bound by the weighted average of candidate risks.

Check Your Understanding

Use the definitions and results above to answer these questions.

Why does the convex-hull oracle risk never exceed the best-single-predictor oracle risk, even when the loss is not convex?
For a convex loss, what inequality relates \(R(f_w)\) to the weighted average of the dictionary risks?
In the squared-error example with constant predictors 0 and 2, what weight on the predictor 2 minimizes risk, and what is that risk?
Why is an input-dependent choice of weights not generally a member of the convex hull defined in this tutorial?
Can the hull-oracle risk equal the dictionary-oracle risk? Give the condition on an optimizing hull predictor that would make equality possible.