Minimax Comparison of Selection and Convex Aggregation

Two benchmarks, two sources of error

A finite dictionary offers two different benchmarks. One is the risk of its best individual predictor; the other is the smallest risk among all convex combinations of its predictors. The second benchmark can be better because averaging may cancel prediction errors. But estimating a useful combination can cost more than identifying one good member. A rate comparison therefore has to keep two quantities separate: the oracle-risk gap and the estimation penalty.

Consider a regression problem with a random pair $(X,Y)$, a dictionary $f_1,\ldots,f_M$, and squared risk $R(f)=E[(Y-f(X))^2]$. Assume $|Y|\le B$ and $|f_j(X)|\le B$ almost surely for every $j$, where $B<\infty$. For a weight vector $\lambda$ in the simplex $\Lambda_M=\{\lambda\in[0,1]^M:\sum_{j=1}^M\lambda_j=1\}$, write $f_\lambda=\sum_{j=1}^M\lambda_j f_j$. The bounds ensure the losses are bounded; they do not assert that a particular dictionary has any specified risk gap.

Definition: The selection oracle risk is $R_{\mathrm{sel}}=\min_{1\le j\le M}R(f_j)$. The convex-hull oracle risk is $R_{\mathrm{conv}}=\inf_{\lambda\in\Lambda_M}R(f_\lambda)$. Their difference $\Delta=R_{\mathrm{sel}}-R_{\mathrm{conv}}$ is nonnegative and measures the improvement in approximation available from convex aggregation.

The infimum in the convex-hull definition is a minimum: $\Lambda_M$ is compact, and $R(f_\lambda)$ is a continuous quadratic function of $\lambda$. Selection is the special case of aggregation that restricts the weights to put all mass on one member.

Squared loss makes the oracle gap explicit

The squared-loss identity below shows what convex aggregation can gain. Let $\eta(X)=E[Y\mid X]$, which exists under the boundedness assumption. The conditional-mean decomposition gives $R(f)=E[(Y-\eta(X))^2]+E[(f(X)-\eta(X))^2]$. The first term is common to every predictor. Thus the improvement depends on how the predictors sit around the regression function, not on the irreducible noise.

Result: For every $\lambda\in\Lambda_M$, $$ \sum_{j=1}^M\lambda_jR(f_j)-R(f_\lambda) = E\left[\sum_{j=1}^M\lambda_j\{f_j(X)-f_\lambda(X)\}^2\right]\ge 0. $$ In particular, convex aggregation cannot have a larger oracle risk than selection.

To prove the identity, first cancel the common term $E[(Y-\eta(X))^2]$ using the conditional-mean decomposition. For each fixed $X$, expand the weighted squared deviations: $$ \sum_{j=1}^M\lambda_j(f_j-\eta)^2-(f_\lambda-\eta)^2 = \sum_{j=1}^M\lambda_jf_j^2-f_\lambda^2 = \sum_{j=1}^M\lambda_j(f_j-f_\lambda)^2. $$ The first equality uses $\sum_j\lambda_j=1$ and $f_\lambda=\sum_j\lambda_jf_j$; expanding the final expression gives the second. Taking expectations proves the identity. Its right-hand side is nonnegative because it is an expectation of a weighted sum of squares. $\square$

Worked Example: Averaging Removes Opposing Errors

Suppose $X$ is constant, $Y=1$ with probability one, and the dictionary consists of $f_1(X)=0$ and $f_2(X)=2$. Each predictor is bounded, as is $Y$.

The two individual risks are $R(f_1)=(1-0)^2=1$ and $R(f_2)=(1-2)^2=1$, so $R_{\mathrm{sel}}=1$. Giving each predictor weight $1/2$ yields $f_\lambda=(0+2)/2=1$ and $R(f_\lambda)=(1-1)^2=0$. Hence $R_{\mathrm{conv}}=0$ and $\Delta=1$.

The identity verifies this gain directly: the weighted disagreement is $\{(0-1)^2+(2-1)^2\}/2=1$, equal to $\sum_j\lambda_jR(f_j)-R(f_\lambda)=1-0$. This is a real oracle advantage, not a claim that every dictionary benefits equally from averaging.

Minimax rates and their regimes

An oracle risk is a benchmark, not the risk achieved from a finite sample. A minimax excess-risk rate describes the order of the smallest worst-case excess over a specified class of bounded problems. For $M\ge2$, the standard finite-dictionary aggregation rates, up to positive constants depending on $B$, are $$ \psi_{\mathrm{sel}}(M,n)=\min\left\{\frac{\log M}{n},1\right\}, \qquad \psi_{\mathrm{conv}}(M,n)= \min\left\{ \begin{cases} M/n,& M\le\sqrt n,\\ \sqrt{\log(1+M/\sqrt n)/n},&M>\sqrt n, \end{cases} 1 \right\}. $$ Here “minimax” refers to worst-case distributions and bounded dictionaries in a rich class; it is not a lower bound for every fixed dictionary. In that worst-case sense, neither rate can in general be improved in order uniformly over the class. For $M=1$, both problems have zero aggregation excess, since there is only one available predictor.

These regimes show why comparing the two oracle risks alone is not enough. Selection pays a logarithmic-in-$M$ penalty. Convex aggregation pays $M/n$ when the dictionary is relatively small, then enters a slower regime once $M$ exceeds $\sqrt n$. Both rates are also bounded above in order by a constant, as reflected by the cap at 1.

If $2\le M\le\sqrt n$.
The convex rate is $M/n$, while the selection rate is $\log M/n$. Their ratio before the constant cap is $M/\log M$. For growing $M$ in this range, the convex-hull estimation rate is larger in order.

If $M>\sqrt n$.
The convex rate is $\sqrt{\log(1+M/\sqrt n)/n}$, until it reaches the constant cap. This can be substantially larger than $\log M/n$; the convex oracle must provide a correspondingly larger risk reduction to pay for it.

Compare the full guarantees.
Subtract the oracle gap from the convex benchmark and compare the resulting penalized risks. A rate advantage by itself does not tell which method is better on a particular distribution.

The boundary $M=\sqrt n$ is consistent on both sides: the low-dimensional expression is $1/\sqrt n$, and the high-dimensional expression is $\sqrt{\log 2/n}$, which has the same order. The two formulas describe a change of regime, not a discontinuous jump.

Worked Example: A Small Dictionary at a Large Sample Size

Take $n=400$ and $M=10$. Since $\sqrt n=20$, this is the $M\le\sqrt n$ regime. The rate expressions, omitting their problem-dependent constants, are $$ \psi_{\mathrm{sel}}=\frac{\log 10}{400}\approx 0.00576, \qquad \psi_{\mathrm{conv}}=\frac{10}{400}=0.025. $$

Thus the convex rate expression is about $0.025/0.00576\approx4.34$ times the selection expression. This does not establish that selection has lower risk: the convex oracle may be substantially better. It says only that, at the rate level, convex aggregation must make up for a larger estimation penalty in this regime.

Worked Example: How Large Must the Hull Advantage Be?

Take $n=10{,}000$ and $M=100$, so $M=\sqrt n$. The two rate expressions are $$ \psi_{\mathrm{sel}}=\frac{\log 100}{10{,}000}\approx0.000461, \qquad \psi_{\mathrm{conv}}=\frac{100}{10{,}000}=0.01. $$

For a transparent comparison, suppose the achieved procedures satisfy oracle inequalities with unit constants: their risks are bounded by $R_{\mathrm{sel}}+\psi_{\mathrm{sel}}$ and $R_{\mathrm{conv}}+\psi_{\mathrm{conv}}$. The convex guarantee is smaller whenever $$ R_{\mathrm{conv}}+0.01<R_{\mathrm{sel}}+0.000461, \quad\text{equivalently}\quad \Delta>0.01-0.000461=0.009539. $$

The calculation is an exact comparison of these stipulated bounds, not a claim that unit constants hold for all procedures or problems. With general constants $A$ and $C$, selection and convex bounds of the form $R_{\mathrm{sel}}+A\psi_{\mathrm{sel}}$ and $R_{\mathrm{conv}}+C\psi_{\mathrm{conv}}$ favor convex aggregation when $\Delta>C\psi_{\mathrm{conv}}-A\psi_{\mathrm{sel}}$.

When the comparison changes with dictionary size

For moderate $M$, the first convex regime makes the contrast especially clear: $M/n$ increases linearly with dictionary size, whereas the selection penalty grows only as $\log M/n$. For example, at fixed $n$, increasing $M$ from a small number can make the convex estimation cost much larger than the selection cost, even though the convex oracle can only improve. The right question is whether that improvement is large enough, not whether convex aggregation is universally preferable.

Above $\sqrt n$, the high-dimensional convex expression grows with $\log(1+M/\sqrt n)$, with a square root over the whole factor $1/n$. In settings where this expression is below its cap, compare it directly with $\log M/n$; if the uncapped rates exceed a constant, the capped rates are the relevant order. Very large dictionaries therefore do not justify extrapolating an uncapped formula indefinitely.

Worked Example: A Dictionary Beyond the Boundary

Let $n=10{,}000$ and $M=1{,}000$. Here $\sqrt n=100$, so the high-dimensional convex regime applies. Its uncapped expression is $$ \sqrt{\frac{\log(1+1{,}000/100)}{10{,}000}} =\sqrt{\frac{\log 11}{10{,}000}} \approx\sqrt{0.0002398} \approx0.0155. $$ The selection expression is $\log(1{,}000)/10{,}000\approx0.000691$. Their ratio is about $22.4$. Thus, at the level of these rate expressions, convex aggregation has a substantial estimation-cost premium. A convex-hull oracle advantage can still make it worthwhile, but dictionary size alone cannot establish that it does.

Common mistake: treating the oracle gap as a rate

A common mistake is to read “the convex-hull risk is no larger” as “convex aggregation must perform better.” The inequality $R_{\mathrm{conv}}\le R_{\mathrm{sel}}$ compares population benchmarks only. It says nothing by itself about the sample-based procedures’ estimation errors. Conversely, seeing that $\psi_{\mathrm{conv}}$ is larger does not prove selection is better: the hull may reduce oracle risk enough to outweigh that cost.

The minimax lower bounds have a related limitation. They concern worst cases over a class of problems. They do not say that every fixed dictionary incurs its worst-case rate, nor do they identify the oracle gap in an individual application. To make a problem-specific comparison, assess both the attainable oracle risks and the constants and conditions in the available oracle inequalities.

Key takeaway: Convex aggregation offers a potentially better oracle, but generally a larger minimax estimation cost. It yields a genuine improvement when its reduction in oracle risk is larger than the extra estimation cost; the minimax rate comparison alone cannot decide that question for a particular dictionary.

Check Your Understanding

Use the definitions and rate regimes to answer the following questions.

Why must $R_{\mathrm{conv}}\le R_{\mathrm{sel}}$, and what does the squared-loss identity say about the source of a strict inequality?
For $M=16$ and $n=1{,}024$, which convex-aggregation regime applies? Write the selection and convex rate expressions before constants.
If an oracle inequality has convex penalty $C\psi_{\mathrm{conv}}$ and selection penalty $A\psi_{\mathrm{sel}}$, state the condition on $\Delta$ that makes the convex bound smaller.
Why does a minimax lower bound over bounded dictionaries not imply that a particular dictionary incurs that rate?
In the example with predictors 0 and 2 and response 1, verify the oracle gap using both the risks and the weighted-disagreement identity.