Comparing Hard Selection And Weighted Aggregation

Two Ways to Use a Finite Prediction Dictionary

Suppose a prediction problem supplies a finite dictionary of \(M\) candidate prediction rules. One approach is hard selection: choose a single candidate with the smallest squared error on the observed data. Another is weighted aggregation: combine the candidates using nonnegative weights that sum to one, choosing the weights to minimize squared error. The comparison is useful because it separates a simple empirical fact—an optimized aggregate can always reproduce any selected candidate—from the more delicate question of how well either data-chosen procedure predicts new observations.

For observations \((X_i,Y_i)\), \(i=1,\ldots,n\), write \(f_j(X_i)\) for candidate \(j\)'s prediction. The definitions below concern squared-error risk on this same data set. No independence or distributional assumption is needed for the empirical comparison.

Definition: The empirical squared risk of candidate \(j\) is \(\widehat R_j=n^{-1}\sum_{i=1}^n(Y_i-f_j(X_i))^2\). A hard-selection oracle is any index \(\hat j\in\arg\min_{1\leq j\leq M}\widehat R_j\); its risk is \(\min_j\widehat R_j\). The simplex is \(\Delta_M=\{w\in\mathbb R^M:w_j\geq0,\ \sum_{j=1}^M w_j=1\}\). For \(w\in\Delta_M\), the aggregate prediction is \(f_w(x)=\sum_{j=1}^M w_jf_j(x)\). A simplex-weighted least-squares aggregate uses any \(\hat w\in\arg\min_{w\in\Delta_M}\widehat R(w)\), where \(\widehat R(w)=n^{-1}\sum_{i=1}^n(Y_i-f_w(X_i))^2\).

The word “oracle” refers to the best candidate in the given dictionary under the specified empirical criterion; it does not mean that the index was known in advance. The weight minimizer exists: the simplex is compact, and \(\widehat R(w)\) is a continuous function of \(w\). The minimizing weights need not be unique, although their fitted prediction vectors agree on the observed points whenever the squared-error minimum is unique as a vector.

Worked Empirical Comparisons

Worked Example: A Strict Improvement From Averaging

There are three observations with responses \(Y=(0,1,2)\) and two candidate prediction vectors \(f_1=(0,0,2)\) and \(f_2=(1,1,1)\). First compute the candidates’ empirical risks:

\(\widehat R_1=(0^2+1^2+0^2)/3=1/3\), while \(\widehat R_2=(1^2+0^2+1^2)/3=2/3\). Thus hard selection chooses \(f_1\), with empirical risk \(1/3\).

Let \(w\) be the weight on \(f_1\), so \(1-w\) is the weight on \(f_2\), where \(0\leq w\leq1\). The aggregate prediction vector is \((1-w,1-w,1+w)\). Its residuals, prediction minus response, are \((1-w,-w,w-1)\), and hence

\widehat R(w)=\frac{2(1-w)^2+w^2}{3}.

The numerator is \(2-4w+3w^2\). Its derivative is \(-4+6w\), which vanishes at \(w=2/3\); its second derivative is \(6>0\), so this is the minimum on \([0,1]\). The fitted vector is \((1/3,1/3,5/3)\), with squared residuals \(1/9,4/9,1/9\). Therefore \(\widehat R(2/3)=2/9\), strictly below the hard-selection risk \(1/3\).

The gain here is not a mysterious benefit of adding a new candidate. It comes from a convex combination of the two prediction vectors that lies closer, in squared-error distance, to the observed response vector.

Worked Example: A Boundary Optimum and Equal-Risk Candidates

Let \(Y=(0,0)\), \(f_1=(0,2)\), and \(f_2=(2,0)\). Each candidate has empirical risk \((0^2+2^2)/2=2\), so either candidate is a hard-selection oracle. Write \(w\) for the weight on \(f_1\). The aggregate vector is \((2(1-w),2w)\), giving

\widehat R(w)=\frac{4(1-w)^2+4w^2}{2} =2\big((1-w)^2+w^2\big).

Expanding gives \(2-4w+4w^2\), whose derivative is \(-4+8w\) and whose second derivative is \(8>0\). The minimum occurs at \(w=1/2\), where the predictions are \((1,1)\) and the empirical risk is \((1+1)/2=1\). Thus the aggregate improves on either candidate, despite there being no uniquely best candidate to select. The optimum lies inside the simplex rather than at a vertex.

Worked Example: Empirical Success Does Not Guarantee Population Success

Let \(X\) be irrelevant and let \(Y\) be Bernoulli with \(P(Y=1)=1/4\). The two candidates are constant predictions \(f_1=0\) and \(f_2=1\). For a constant prediction \(q\), its population squared risk is

R(q)=E[(Y-q)^2] =\frac14(1-q)^2+\frac34q^2 =\frac{3}{16}+\left(q-\frac14\right)^2.

Consequently, the population hard-selection oracle has risk \(R(0)=1/4\), while \(R(1)=3/4\). The population-optimal simplex aggregate is the constant \(q=1/4\), with risk \(3/16\). Now take a training sample of size three in which all three responses equal one. This event has probability \((1/4)^3=1/64\). On that sample, candidate 1 has empirical risk \(1\), candidate 2 has empirical risk \(0\), and the least-squares aggregate chooses weight one on candidate 2, also with empirical risk zero. But that fitted prediction has population risk \(3/4\), greater than the population hard-selection oracle’s \(1/4\).

This example does not contradict the empirical comparison: on the observed sample the aggregate attains the minimum empirical risk. It shows why that comparison is not, by itself, a guarantee about the risk on new observations. Both procedures can be misled by an atypical sample.

Why the Empirical Comparison Holds

Two properties clarify what can and cannot be concluded. The first is an exact squared-loss identity for any fixed simplex weights. The second is an oracle comparison for the optimized aggregate.

Theorem: For every \(w\in\Delta_M\), \(\widehat R(w)=\sum_{j=1}^M w_j\widehat R_j-\sum_{i=1}^n n^{-1}\sum_{j=1}^M w_j\{f_j(X_i)-f_w(X_i)\}^2\). In particular, \(\widehat R(w)\leq\sum_jw_j\widehat R_j\). If \(\hat w\) minimizes \(\widehat R(w)\) over \(\Delta_M\), then \(\widehat R(\hat w)\leq\min_j\widehat R_j\).

To prove the identity, fix an observation \(i\) and abbreviate \(a_j=f_j(X_i)\) and \(\bar a=\sum_jw_ja_j=f_w(X_i)\). Expanding the weighted squared deviations gives

\sum_jw_j(a_j-\bar a)^2 =\sum_jw_ja_j^2-\bar a^2,

because \(\sum_jw_j=1\). Expanding the weighted response errors gives \(\sum_jw_j(Y_i-a_j)^2=Y_i^2-2Y_i\bar a+\sum_jw_ja_j^2\), whereas \((Y_i-\bar a)^2=Y_i^2-2Y_i\bar a+\bar a^2\). Subtracting the latter expression from the former yields exactly \(\sum_jw_j(a_j-\bar a)^2\). Thus

(Y_i-\bar a)^2 =\sum_jw_j(Y_i-a_j)^2-\sum_jw_j(a_j-\bar a)^2.

Average this equality over \(i=1,\ldots,n\). The first term on the right becomes \(\sum_jw_j\widehat R_j\), and the second becomes the displayed diversity term in the theorem. That term is nonnegative because it is a weighted sum of squares, proving the first inequality. For the oracle comparison, let \(e_j\) be the simplex vertex with weight one on candidate \(j\). Then \(f_{e_j}=f_j\), so \(\widehat R(\hat w)\leq\widehat R(e_j)=\widehat R_j\) for every \(j\), by the minimizing property of \(\hat w\). Taking the minimum over \(j\) proves the claim. \(\square\)

The identity also explains why the result is specific to an optimized aggregate. A fixed weighted average is bounded above by the weighted average of candidate risks, but that weighted average can exceed the smallest candidate risk. The diversity term can offset the difference, but need not do so enough for every choice of weights. Optimization over the simplex is what ensures the aggregate can do at least as well as the best vertex.

Population Risk and the Assumptions Behind It

For a fresh observation \((X,Y)\), define the population risk \(R_j=E[(Y-f_j(X))^2]\) and, for fixed weights \(w\), \(R(w)=E[(Y-f_w(X))^2]\). If \(E[Y^2]\) and every \(E[f_j(X)^2]\) are finite, all the finite sums and expectations below are well-defined. Applying the same pointwise squared-loss identity and taking expectations gives

R(w)=\sum_jw_jR_j-E\left[\sum_jw_j\{f_j(X)-f_w(X)\}^2\right] \leq\sum_jw_jR_j.

The population simplex optimum, \(\inf_{w\in\Delta_M}R(w)\), is no larger than \(\min_jR_j\), because every candidate is represented by a simplex vertex. This is a population statement about optimizing the population risk. It does not say that the weights \(\hat w\) fitted to a finite sample must satisfy \(R(\hat w)\leq\min_jR_j\). In general, moving from an empirical guarantee to a population guarantee requires assumptions and an argument controlling how empirical risks differ from population risks over the predictors being compared. The Bernoulli example shows that no such conclusion follows from empirical minimization alone.

These distinctions also help interpret the term “risk.” The inequality \(\widehat R(\hat w)\leq\min_j\widehat R_j\) compares training-set errors under one fixed loss and one fixed dictionary. It is an exact optimization fact, not a claim that the aggregate is universally more accurate, that its weights are unique, or that it will generalize better.

Common Pitfall

A common mistake is to say, “A weighted average is always better than the best candidate because squared loss is convex.” Convexity gives \(\widehat R(w)\leq\sum_jw_j\widehat R_j\); it does not imply \(\widehat R(w)\leq\min_j\widehat R_j\) for arbitrary weights. For example, if the candidate risks are \(0\) and \(4\), assigning weight \(1/2\) to each only yields the convexity upper bound \(2\), which is not below the best risk \(0\). The correction is to distinguish a chosen mixture from the least-squares optimizer: the optimizer is no worse than the best candidate empirically because the simplex includes every candidate as a vertex. Neither that fact nor convexity alone establishes a population-risk advantage for sample-fitted weights.

Key takeaway: On a fixed data set with squared loss, simplex least-squares aggregation cannot have greater empirical risk than hard selection, because it optimizes over a set containing every hard choice. Whether its sample-fitted weights have lower population risk is a separate question requiring control of generalization.

Check Your Understanding

Use the definitions and comparisons above to answer the following.

Why does the simplex-weighted least-squares minimum always have empirical risk no greater than the hard-selection oracle?
What does the diversity term in the squared-loss identity measure, and why is it nonnegative?
Can a fixed simplex-weighted average have greater empirical risk than the best individual candidate? Explain what the oracle comparison does and does not say.
In the Bernoulli example, what is the probability of the all-ones training sample, and what are the fitted aggregate’s empirical and population risks?
State one assumption needed to define the population squared risks used in the tutorial.