Convex-Aggregation Rates for Bounded Squared Loss

Why Compare with the Convex Hull?

A finite dictionary contains $M$ candidate regression functions, but its best individual member need not be its best available prediction. A weighted average of candidates can have lower risk than every candidate separately. Convex aggregation asks whether data can be used to approach the best such average, rather than only to select one dictionary member.

Here we study a direct answer under bounded squared loss: minimize empirical risk over the dictionary’s convex hull, then compare the resulting predictor with the predictor of lowest population risk in that same hull. A finite-sample bound will show how the cost of this comparison depends on the dictionary size and sample size. The bound proved here is a general finite-dimensional guarantee; it is not a claim that this particular bound is the sharpest possible rate.

Definition: Let $(X_i,Y_i)_{i=1}^n$ be independent and identically distributed observations, and let $f_1,\ldots,f_M$ be fixed measurable regression functions taking values in $[0,1]$. The convex hull of the dictionary is $$ \mathcal{C}=\left\{f_\theta=\sum_{j=1}^M\theta_j f_j:\ \theta\in\Delta_M\right\},\qquad \Delta_M=\left\{\theta\in[0,1]^M:\sum_{j=1}^M\theta_j=1\right\}. $$ Assume $Y_i\in[0,1]$ almost surely. For $f\in\mathcal{C}$, define its squared-loss risk and empirical risk by $R(f)=E[(Y-f(X))^2]$ and $R_n(f)=n^{-1}\sum_{i=1}^n(Y_i-f(X_i))^2$. An empirical-risk aggregate is any $\hat f\in\mathcal{C}$ minimizing $R_n(f)$ over $f\in\mathcal{C}$. A best convex-hull predictor is any $f^*\in\mathcal{C}$ minimizing $R(f)$ over $\mathcal{C}$.

The simplex $\Delta_M$ is compact, and the risks are continuous functions of the weights, so both minimizers exist. Convex combinations of functions in $[0,1]$ remain in $[0,1]$; consequently the squared losses lie in $[0,1]$. We measure performance by the excess risk $R(\hat f)-R(f^*)$, not by the difference between the two empirical risks.

Worked Example: A Mixture Beats Either Candidate

Suppose $X$ is irrelevant, $Y$ is Bernoulli with success probability $1/2$, and the dictionary consists of the constant predictors $f_1=0$ and $f_2=1$. Every convex combination is a constant $f_\theta=\theta$, where $0\leq\theta\leq1$.

For any constant $a$, the risk is $$ R(a)=E[(Y-a)^2]=\tfrac12(0-a)^2+\tfrac12(1-a)^2 =a^2-a+\tfrac12=(a-\tfrac12)^2+\tfrac14. $$ Thus the best convex-hull predictor is $f^*=1/2$, with risk $1/4$. Each dictionary member has risk $1/2$, so restricting the comparator to one candidate would lose $1/4$ in risk.

For a sample with $\bar Y=n^{-1}\sum_{i=1}^nY_i$, the empirical risk of a constant $a$ is minimized at $a=\bar Y$, which is in $[0,1]$. Therefore $\hat f=\bar Y$. Its population excess risk is $R(\bar Y)-R(1/2)=(\bar Y-1/2)^2$, and $$ E[R(\hat f)-R(f^*)]=\operatorname{Var}(\bar Y)=\frac{1}{n}\operatorname{Var}(Y)=\frac{1}{4n}. $$ This calculation makes the comparator important: the empirical aggregate is being assessed against the attainable mixture, not against the best single constant.

The Geometry Behind a Fast Comparison

Squared loss has a useful decomposition. Since $f^*$ minimizes risk over the convex set $\mathcal{C}$, moving from $f^*$ toward any $h\in\mathcal{C}$ cannot decrease risk to first order. This fact makes the excess risk control the squared distance between the predictors.

Result: For every $h\in\mathcal{C}$, $$ R(h)-R(f^*)\geq E[(h(X)-f^*(X))^2]. $$

To prove it, consider $f_t=f^*+t(h-f^*)$ for $0\leq t\leq1$. Convexity of $\mathcal{C}$ ensures $f_t\in\mathcal{C}$. Expanding the risk gives $$ R(f_t)=R(f^*)+2tE[(f^*(X)-Y)(h(X)-f^*(X))]+t^2E[(h(X)-f^*(X))^2]. $$ Because $t=0$ minimizes this expression on $[0,1]$, its right derivative at zero is nonnegative. Hence $2E[(f^*(X)-Y)(h(X)-f^*(X))]\geq0$. Expanding $R(h)-R(f^*)$ and using this inequality proves the result. $\square$

The next bound is a finite-sample consequence. Its logarithmic factor comes from covering the simplex by a finite net, and its $1/n$ scale comes from concentration around the population minimizer.

Theorem: Under the boundedness and independence assumptions above, for $n\geq2$ and $0<\delta<1$, an empirical-risk aggregate satisfies, with probability at least $1-\delta$, $$ R(\hat f)-R(f^*)\leq \frac{10+100\left\{M\log(1+2n)+\log(1/\delta)\right\}}{n}. $$ The excess risk is also always at most $1$, so the right side may be replaced by its minimum with $1$.

Proof. First, the squared-loss difference between any two predictors $h,g\in\mathcal{C}$ is $$ Z=(Y-h(X))^2-(Y-g(X))^2=(h(X)-g(X))(h(X)+g(X)-2Y). $$ Since $h(X),g(X),Y$ lie in $[0,1]$, $|h(X)+g(X)-2Y|\leq2$, so $|Z|\leq2|h(X)-g(X)|$. Also, each squared loss lies in $[0,1]$, hence $Z\in[-1,1]$. Therefore, $\operatorname{Var}(Z)\leq E[Z^2]\leq4E[(h(X)-g(X))^2]$.

Fix a number $\varepsilon\in(0,1)$. There is an $\varepsilon$-net of $\Delta_M$ in $\ell_1$ distance with at most $(1+2/\varepsilon)^M$ points. Equivalently, for every weight vector there is a net point within $\varepsilon$ in $\ell_1$. If $\theta,\eta\in\Delta_M$, then $$ |f_\theta(x)-f_\eta(x)|\leq\sum_{j=1}^M|\theta_j-\eta_j||f_j(x)|\leq\|\theta-\eta\|_1. $$ Since $u\mapsto(y-u)^2$ is 2-Lipschitz on $[0,1]$, predictors whose weights are within $\varepsilon$ have both empirical and population risks within $2\varepsilon$.

Let $g$ be a net predictor within $\varepsilon$ of $f^*$. For any net predictor $h$, write $\Delta=R(h)-R(f^*)$ and $Z_i=(Y_i-h(X_i))^2-(Y_i-f^*(X_i))^2$. The result just proved gives $E[(h-f^*)^2]\leq\Delta$, so $\operatorname{Var}(Z_i)\leq4\Delta$. Also $E[Z_i]=\Delta$, and $Z_i\in[-1,1]$. Bernstein’s inequality therefore implies, for $0<x\leq\Delta$, $$ P\left(\frac1n\sum_{i=1}^n Z_i-\Delta\leq-x\right) \leq \exp\left(-\frac{nx^2}{2(4\Delta+2x/3)}\right). $$ On the event $R_n(h)-R_n(f^*)\leq4\varepsilon$, if $\Delta>8\varepsilon$, the deviation is at least $\Delta-4\varepsilon\geq\Delta/2$. Substituting $x=\Delta/2$ in Bernstein’s inequality bounds this event by $\exp(-3n\Delta/104)$. A union bound over the net shows that, with probability at least $1-\delta$, every net point satisfying the empirical-risk inequality has $$ \Delta\leq 8\varepsilon+\frac{100}{n}\left\{M\log(1+2/\varepsilon)+\log(1/\delta)\right\}. $$ Indeed, above this threshold the exponential tail is smaller than $\delta$ divided by the net’s cardinality.

It remains to apply this statement to the actual empirical minimizer. Choose a net predictor $h$ within $\varepsilon$ of $\hat f$. Empirical minimization gives $R_n(\hat f)\leq R_n(g)$, and the risk approximation bound gives $$ R_n(h)-R_n(f^*)\leq 2\varepsilon+2\varepsilon+2\varepsilon=6\varepsilon, $$ which is at most $4\varepsilon$ if the net approximation is applied directly to the two predictors $\hat f$ and $f^*$: specifically, $R_n(h)-R_n(f^*)\leq R_n(\hat f)-R_n(f^*)+2\varepsilon\leq 4\varepsilon$, since $R_n(\hat f)\leq R_n(g)\leq R_n(f^*)+2\varepsilon$. Thus the net bound applies to $h$. Finally, $R(\hat f)\leq R(h)+2\varepsilon$. Set $\varepsilon=1/n$; then $\log(1+2/\varepsilon)=\log(1+2n)$, yielding the stated inequality. $\square$

Interpreting the Rate

For fixed confidence level, the displayed guarantee has order $M\log(n)/n$, up to constants and the confidence term. When the dictionary is small relative to the sample size, increasing $n$ reduces the bound at a $1/n$ scale. The bound also records the price of searching across $M$ weights. If it exceeds $1$, the trivial bound from losses in $[0,1]$ is more informative.

Worked Example: Evaluating the Bound at a Fixed Sample Size

Take $M=5$, $n=10{,}000$, and confidence level $1-\delta=0.95$, so $\delta=0.05$. The dimension-and-sample term is $$ \frac{M\log(1+2n)}{n} =\frac{5\log(20{,}001)}{10{,}000} \approx\frac{5(9.9035)}{10{,}000} \approx0.004952. $$ The confidence term is $\log(1/\delta)/n=\log(20)/10{,}000\approx2.9957/10{,}000\approx0.000300$. Substituting into the theorem gives $$ \frac{10+100(49.5177+2.9957)}{10{,}000} \approx0.526. $$ This is a valid but conservative numerical bound. The calculation illustrates why a theorem with explicit universal constants can be useful for its scaling conclusion even when its numerical guarantee is loose.

This comparison is specifically with the best convex combination. A selection guarantee instead compares with $\min_j R(f_j)$, the risk of the best individual candidate. Those are different targets: the Bernoulli example shows that the convex-hull risk can be strictly smaller. Nor should the theorem’s $M\log(n)/n$ bound be read as a universal sharp rate for every convex-aggregation problem; sharper aggregation guarantees require more tailored arguments and assumptions.

Worked Example: Comparing the Complexity Terms

Suppose $M=20$ and $n=5{,}000$. The dimension term appearing in the theorem, before its universal constant, is $$ \frac{M\log(1+2n)}{n} =\frac{20\log(10{,}001)}{5{,}000} \approx\frac{20(9.2104)}{5{,}000} \approx0.03684. $$ For comparison, a finite-dictionary selection penalty involving $\log(M)/n$ has scale $$ \frac{\log(20)}{5{,}000}\approx\frac{2.9957}{5{,}000}\approx0.000599. $$ These terms have different comparators: the latter is associated with the cost of choosing among individual candidates, while the convex-hull bound controls risk against a possibly better mixture. The numerical comparison alone does not establish which procedure has lower risk; it displays the different complexity terms and targets.

Worked Example: Verifying the Empirical Mixture

Return to the two predictors $0$ and $1$ with $Y_i$ independent Bernoulli$(1/2)$. A mixture with weight $a$ on predictor $1$ predicts the constant $a$. Its empirical risk is $$ R_n(a)=\frac1n\sum_{i=1}^n(Y_i-a)^2 =\frac1n\sum_{i=1}^nY_i^2-2a\bar Y+a^2 =\bar Y-2a\bar Y+a^2. $$ Completing the square gives $R_n(a)=\bar Y-\bar Y^2+(a-\bar Y)^2$. Since $\bar Y\in[0,1]$, the empirical minimizer over all mixtures is exactly $a=\bar Y$, not necessarily either endpoint. Its excess population risk is $(\bar Y-1/2)^2$, whose expectation is $1/(4n)$, as calculated earlier. Thus in this concrete case the empirical-risk aggregate does approach the best convex-hull predictor at a $1/n$ expected-risk scale.

Common Pitfall

A tempting but incorrect argument is: “There are $M$ predictors, so the finite-class selection bound immediately controls empirical minimization over their convex hull.” The convex hull is not the original finite class; it contains infinitely many weight vectors. A union bound over only the $M$ vertices does not control all mixtures, and its comparator may be worse than the best mixture. The proof above addresses this by covering the simplex and controlling the resulting finite net. It is the net size, rather than simply the number of original predictors, that enters this particular argument.

Key takeaway: Under bounded squared loss, empirical minimization over a finite dictionary’s convex hull admits a finite-sample excess-risk guarantee of order $M\log(n)/n$ at fixed confidence. The comparator is the best population-risk predictor in the hull; that guarantee is not interchangeable with a bound against the best single dictionary member.

Check Your Understanding

Use the definitions and argument above to answer these questions.

Why does a convex combination of predictors taking values in $[0,1]$ also take values in $[0,1]$?
State the comparator in the theorem, and explain how it differs from the best individual dictionary member.
Where does boundedness enter the Bernstein argument for squared-loss differences?
Why is it not enough to apply a finite-class union bound over the $M$ original predictors?
In the Bernoulli example, derive the empirical minimizer over constant mixtures from the completed-square expression for $R_n(a)$.