Selection Oracles And Aggregation Oracles

Two Different Questions About a Finite Dictionary

Suppose a learning problem supplies a finite collection of candidate prediction functions. One question is: how well can the best single candidate predict? A different question is: how well can a weighted combination of candidates predict? The answers need not be the same. The first is a benchmark for selection; the second is a benchmark for aggregation.

This distinction matters when reading an oracle inequality. An oracle is an ideal comparator, not a procedure that has been run on the data. A guarantee relative to the best dictionary member is not automatically a guarantee relative to the best weighted combination. The comparator determines the strength of the claim.

Formal Setup and Definitions

Let $(X,Y)$ be a random input and response, and let $f_1,\ldots,f_M$ be a finite dictionary of measurable predictors, where $M\geq 1$. Let $\ell(Y,f(X))$ be a nonnegative measurable loss, and define the risk of a predictor $f$ by

R(f)=E[\ell(Y,f(X))].

Assume the risks of the dictionary members are finite. When considering combinations, assume predictions take values in a convex set $C$, and that the combinations under discussion are measurable and have well-defined risk. The population distribution and dictionary are fixed; a learning procedure may nevertheless produce a data-dependent predictor.

Definition: The selection oracle risk is the smallest risk among the individual dictionary members: $$ R_{\mathrm{sel}}^*=\min_{1\leq j\leq M} R(f_j). $$ The aggregation oracle risk, under the deterministic convex-aggregation convention used here, is the smallest risk among convex combinations of their predictions: $$ R_{\mathrm{agg}}^*=\inf_{\lambda\in\Delta_M} R(f_\lambda), \qquad f_\lambda(x)=\sum_{j=1}^M\lambda_j f_j(x), \qquad \Delta_M=\left\{\lambda\in[0,1]^M:\sum_{j=1}^M\lambda_j=1\right\}. $$

A convex combination uses one fixed weight vector $\lambda$ across inputs. It is a prediction function in its own right; it need not equal any one of the dictionary members. In particular, the aggregation oracle is not the same benchmark as selecting a random index $J$ with probabilities $\lambda_j$ and then using $f_J$. That randomized procedure has expected risk

E[R(f_J)]=\sum_{j=1}^M\lambda_jR(f_j),

which averages the risks of individual candidates. A deterministic combination instead first combines predictions and then evaluates the loss. Those operations can give different answers.

Worked Example: A Combination Beats Either Candidate

Suppose $Y=0$ with probability one, the dictionary consists of the constant predictors $f_1(x)=-1$ and $f_2(x)=1$, and the loss is squared error, $\ell(Y,a)=(Y-a)^2$. The input $X$ is irrelevant.

For either dictionary member, the risk is

R(f_1)=(0-(-1))^2=1, \qquad R(f_2)=(0-1)^2=1.

Thus $R_{\mathrm{sel}}^*=1$. With weight $\lambda$ on $f_2$, the combined prediction is

f_\lambda=(1-\lambda)(-1)+\lambda(1)=2\lambda-1.

Its risk is $R(f_\lambda)=(2\lambda-1)^2$, which is nonnegative for every $\lambda\in[0,1]$ and equals zero at $\lambda=1/2$. Therefore $R_{\mathrm{agg}}^*=0$. A guarantee as good as the selection oracle would still leave a gap of one relative to the aggregation oracle in this example.

Worked Example: The Best Weight Need Not Be One Half

Let $Y=1$ with probability one, use squared error, and take two constant predictors $f_1=0$ and $f_2=4$. The selection risks are

R(f_1)=(1-0)^2=1, \qquad R(f_2)=(1-4)^2=9.

Consequently, $R_{\mathrm{sel}}^*=1$. If $\lambda$ is the weight on $f_2$, then $f_\lambda=4\lambda$, so

R(f_\lambda)=(1-4\lambda)^2.

This is a square and is therefore at least zero; it equals zero precisely when $1-4\lambda=0$, or $\lambda=1/4$. This weight is in $[0,1]$, so $R_{\mathrm{agg}}^*=0$. The example also shows why it is not enough to compare only an equal-weight average with the candidates: the aggregation oracle optimizes over all weights in the simplex.

How the Benchmarks Are Related

Every individual candidate is an allowed convex combination: choose weight one on that candidate and zero on all others. This simple containment gives a general ordering, regardless of whether the loss is convex.

Theorem: Under the definitions above, $$ R_{\mathrm{agg}}^*\leq R_{\mathrm{sel}}^*. $$

Proof. Let $j^*$ be an index attaining the minimum $R_{\mathrm{sel}}^*$, which exists because the dictionary is finite. Let $e_{j^*}\in\Delta_M$ put weight one on coordinate $j^*$ and zero on every other coordinate. Then $f_{e_{j^*}}=f_{j^*}$. Since the aggregation oracle takes an infimum over a set containing $e_{j^*}$,

R_{\mathrm{agg}}^* =\inf_{\lambda\in\Delta_M}R(f_\lambda) \leq R(f_{e_{j^*}}) =R(f_{j^*}) =R_{\mathrm{sel}}^*.

This establishes the ordering. It does not say that the inequality is strict: the two oracle risks can be equal, or the aggregation oracle can be strictly better. $\square$

An oracle inequality makes a different comparison: it bounds the risk of a procedure's output against a chosen benchmark, often with a remainder term. For example, a selection-type statement has the form

R(\hat f)\leq R_{\mathrm{sel}}^*+\Delta_n,

where $\hat f$ may depend on the training data and $\Delta_n$ is a nonnegative remainder. An aggregation-type statement replaces $R_{\mathrm{sel}}^*$ by $R_{\mathrm{agg}}^*$. Such inequalities may be asserted deterministically or on a specified probability event; either way, the benchmark written on the right-hand side is essential to interpreting the claim.

Result: On any event where an aggregation-type inequality holds, the same inequality also implies a selection-type inequality with the same remainder. The reverse implication does not hold in general.

Proof. If $R(\hat f)\leq R_{\mathrm{agg}}^*+\Delta_n$, the benchmark ordering gives $R_{\mathrm{agg}}^*\leq R_{\mathrm{sel}}^*$. Adding $\Delta_n$ to both sides preserves the ordering, so

R(\hat f)\leq R_{\mathrm{agg}}^*+\Delta_n \leq R_{\mathrm{sel}}^*+\Delta_n.

For the reverse direction, the first worked example has $R_{\mathrm{sel}}^*=1$ and $R_{\mathrm{agg}}^*=0$. A procedure that always outputs $f_1$ has $R(\hat f)=1$, and so satisfies the exact selection inequality $R(\hat f)\leq R_{\mathrm{sel}}^*$. It does not satisfy an aggregation inequality with remainder $\Delta_n=1/2$, since $1\not\leq 0+1/2$. Thus a selection guarantee alone cannot establish an aggregation guarantee. $\square$

Worked Example: Reading an Oracle Claim Correctly

Use the predictors and squared-error risks from the second worked example. Suppose a procedure always returns $f_1=0$, so its risk is $1$. The selection oracle risk is also $1$, while the aggregation oracle risk is $0$.

With remainder $\Delta_n=0.2$, the selection comparison is valid:

R(\hat f)=1\leq 1+0.2=R_{\mathrm{sel}}^*+0.2.

The corresponding aggregation comparison is not valid:

R(\hat f)=1\not\leq 0+0.2=R_{\mathrm{agg}}^*+0.2.

Nothing about the first inequality makes the second true. To claim performance relative to the aggregation oracle, one needs a bound that actually uses that benchmark, with an appropriate remainder.

What an Oracle Bound Does—and Does Not—Say

An oracle benchmark describes the quality of an ideal comparator, not the form of the procedure's output. A selection oracle asks how well one dictionary member performs; an aggregation oracle asks how well the best permitted weighted prediction performs. The fact that a procedure outputs a combination does not, by itself, prove that it is close to the aggregation oracle. Likewise, a procedure that returns a single member can still be assessed against the aggregation oracle, but that is a stronger claim and may fail when combinations substantially improve risk.

The distinction is especially important when comparing results stated with different remainders. A bound with a smaller remainder is not automatically stronger if it uses a worse benchmark. For instance, $R_{\mathrm{sel}}^*+\Delta_n$ can exceed $R_{\mathrm{agg}}^*+\Delta_n$ by a substantial amount. To compare two guarantees, inspect both the oracle risk and the remainder, as well as whether the statement is deterministic or holds with a stated probability.

Common Mistake

Wrong reasoning: “A procedure is guaranteed to be nearly as good as the best dictionary member, so it is also nearly as good as the best weighted combination.”

The conclusion does not follow. The aggregation oracle risk is no larger than the selection oracle risk, and it can be strictly smaller. A bound above the larger benchmark can leave too much room to guarantee proximity to the smaller one. The correction is to name the comparator explicitly: a selection oracle inequality compares with $\min_j R(f_j)$; an aggregation oracle inequality compares with $\inf_{\lambda\in\Delta_M}R(f_\lambda)$. Do not upgrade one claim to the other without a separate argument.

Key takeaway: The oracle is part of the guarantee. Selection benchmarks the best single dictionary member; aggregation benchmarks the best fixed convex combination. Aggregation is at least as demanding a comparator, and a selection bound alone does not establish it.

Check Your Understanding

For each question, identify the benchmark involved and justify your answer.

Why is every dictionary member available to the aggregation oracle?
Can the aggregation oracle risk be larger than the selection oracle risk under these definitions? Explain.
What is the difference between a deterministic convex combination of predictions and random selection of one dictionary member?
If a procedure satisfies an aggregation oracle inequality on an event, what selection inequality follows on that same event?
Why does a selection oracle inequality not, in general, imply an aggregation oracle inequality with the same remainder?