Oracle Inequalities for Data-Fitted Stacking Weights

Why an Oracle Inequality for Stacking?

Stacking chooses weights for a collection of candidate predictors using data. Its empirical objective can be optimized accurately, but the quantity of interest is population risk. An oracle inequality makes the link precise: it bounds the population risk of the fitted weights by the risk of the best population weights in the allowed class, plus terms for empirical risk error and imperfect empirical optimization.

The central condition is uniformity. A risk bound that holds simultaneously for every weight vector in the simplex also holds for a vector selected after looking at the validation observations. The candidate predictors must be fixed independently of those observations, conditional on any training data used to construct them. The weights themselves need not be independent of the validation observations.

Setup and Definitions

Suppose there are $K$ candidate predictors $f_1,\ldots,f_K$. Conditional on training data, treat these functions as fixed. Let $(X_i,Y_i)$, $i=1,\ldots,n$, be independent validation observations with the same distribution as a generic pair $(X,Y)$, and suppose they are independent of the training data. For a weight vector $w=(w_1,\ldots,w_K)$, the stacked prediction is $f_w(x)=\sum_{j=1}^K w_j f_j(x)$.

Definition: The simplex of stacking weights is $\Delta_K=\{w\in\mathbb{R}^K:w_j\geq 0\text{ for all }j,\ \sum_{j=1}^K w_j=1\}$. For a loss function $\ell(y,a)$, the conditional population risk and validation empirical risk are $$ R(w)=E[\ell(Y,f_w(X))\mid\mathcal{T}],\qquad \widehat R_n(w)=\frac{1}{n}\sum_{i=1}^n \ell(Y_i,f_w(X_i)), $$ where $\mathcal{T}$ denotes the training data. The population oracle weight $w^*$ minimizes $R(w)$ over $\Delta_K$; an empirical minimizer $\hat w$ minimizes $\widehat R_n(w)$ over the same simplex.

For the finite-sample result below, assume the loss is measurable, takes values in $[0,1]$, and is $L$-Lipschitz in its prediction argument: $|\ell(y,a)-\ell(y,b)|\leq L|a-b|$. Assume also that $|f_j(x)|\leq B$ for every candidate and every $x$, for a finite constant $B$. These conditions ensure bounded concentration and control how risk changes when the weights change. They are sufficient conditions for this result, not universal requirements for every possible stacking bound.

A Uniform Risk Bound Over the Simplex

Write $\|w-v\|_1=\sum_{j=1}^K|w_j-v_j|$. For any $w,v\in\Delta_K$, $$ |f_w(x)-f_v(x)| =\left|\sum_{j=1}^K(w_j-v_j)f_j(x)\right| \leq B\|w-v\|_1. $$ The Lipschitz condition therefore gives $|\ell(y,f_w(x))-\ell(y,f_v(x))|\leq LB\|w-v\|_1$. This controls both population and empirical risk as the weights vary.

Theorem (finite-grid uniform risk bound): Let $K\geq2$, $0<\delta<1$, and let $m\geq1$ be an integer. Define $$ \mathcal{G}_m=\left\{\left(\frac{a_1}{m},\ldots,\frac{a_K}{m}\right):a_j\in\{0,1,2,\ldots\},\ \sum_{j=1}^K a_j=m\right\},\qquad M_m=|\mathcal{G}_m|=\binom{m+K-1}{K-1}. $$ Conditional on the training data, with probability at least $1-\delta$ over the validation sample, $$ \sup_{w\in\Delta_K}|\widehat R_n(w)-R(w)| \leq \sqrt{\frac{\log(2M_m/\delta)}{2n}}+\frac{4LB(K-1)}{m}. $$

Proof. First fix $w\in\Delta_K$. For each $j<K$, set $a_j=\lfloor mw_j\rfloor$, and set $a_K=m-\sum_{j<K}a_j$. All $a_j$ are nonnegative integers: the sum of the first $K-1$ floors is at most $m\sum_{j<K}w_j\leq m$. The resulting $v=(a_1/m,\ldots,a_K/m)$ belongs to $\mathcal{G}_m$. For $j<K$, $0\leq w_j-a_j/m<1/m$, and the discrepancy in the last coordinate is the sum of these first $K-1$ discrepancies. Consequently, $$ \|w-v\|_1 =\sum_{j<K}(w_j-a_j/m)+\left|w_K-a_K/m\right| <\frac{2(K-1)}{m}. $$

For a fixed grid point $v$, the validation losses are independent, lie in $[0,1]$, and have mean $R(v)$, conditional on the training data. Hoeffding's inequality and a union bound over the $M_m$ grid points give, with conditional probability at least $1-\delta$, $$ \max_{v\in\mathcal{G}_m}|\widehat R_n(v)-R(v)| \leq \sqrt{\frac{\log(2M_m/\delta)}{2n}}. $$ On this event, take any $w\in\Delta_K$ and its grid approximation $v$. The Lipschitz property and the prediction bound imply both $|\widehat R_n(w)-\widehat R_n(v)|\leq LB\|w-v\|_1$ and $|R(w)-R(v)|\leq LB\|w-v\|_1$. Adding these inequalities to the grid-point deviation yields $$ |\widehat R_n(w)-R(w)| \leq \sqrt{\frac{\log(2M_m/\delta)}{2n}}+2LB\|w-v\|_1 \leq \sqrt{\frac{\log(2M_m/\delta)}{2n}}+\frac{4LB(K-1)}{m}. $$ The bound holds for every $w$ on the same event, proving the theorem. $\square$

The first term is a finite-sample concentration term; the second is the cost of approximating the continuous simplex by a finite grid. Choosing a larger $m$ decreases the grid approximation error but increases $M_m$, and hence the concentration term. This bound is explicit rather than necessarily optimal.

Worked Example: Turning a Uniform Bound Into a Risk Guarantee

Suppose a validation analysis with two candidate predictors establishes that, with probability at least $0.95$, $\sup_{w\in\Delta_2}|\widehat R_n(w)-R(w)|\leq0.08$. The fitted weights have empirical risk at most $0.01$ above the minimum empirical risk. Find a bound on their excess population risk over the population oracle.

Let $\hat w$ denote the fitted weights and $w^*$ a population minimizer. Add and subtract the empirical risks: $$ R(\hat w)-R(w^*) =[R(\hat w)-\widehat R_n(\hat w)] +[\widehat R_n(\hat w)-\widehat R_n(w^*)] +[\widehat R_n(w^*)-R(w^*)]. $$

On the stated event, the first and third terms are each at most $0.08$. The empirical optimization condition gives $\widehat R_n(\hat w)-\widehat R_n(w^*)\leq0.01$. Therefore, $$ R(\hat w)-R(w^*)\leq0.08+0.01+0.08=0.17. $$ With an exact empirical minimizer, the middle term is nonpositive and the corresponding bound is $0.16$. These are upper bounds, not claims that the actual excess risk equals those values.

The Oracle Inequality and Its Interpretation

Corollary (oracle inequality): Suppose a bound $\sup_{w\in\Delta_K}|\widehat R_n(w)-R(w)|\leq\varepsilon_n$ holds on an event. If $\hat w\in\Delta_K$ satisfies $\widehat R_n(\hat w)\leq\inf_{w\in\Delta_K}\widehat R_n(w)+\eta$, where $\eta\geq0$, then on that event $$ R(\hat w)\leq\inf_{w\in\Delta_K}R(w)+2\varepsilon_n+\eta. $$

Proof. By uniformity, $R(\hat w)\leq\widehat R_n(\hat w)+\varepsilon_n$. The approximate empirical minimization condition gives $\widehat R_n(\hat w)\leq\widehat R_n(w^*)+\eta$, where $w^*$ minimizes population risk. Applying uniformity once more gives $\widehat R_n(w^*)\leq R(w^*)+\varepsilon_n$. Combining the three inequalities proves the claim. If the population minimum is not attained, the same argument applies to any $w$ and then takes the infimum. $\square$

The decomposition identifies two distinct contributions. The term $2\varepsilon_n$ is the price of using empirical risks to choose weights instead of knowing population risks; $\eta$ is the optimization error. In particular, if the finite-grid theorem supplies $\varepsilon_n$, it gives an oracle guarantee with probability at least $1-\delta$. The comparison is to the best convex combination of the specified candidate predictors, not to every possible prediction rule. A small oracle gap does not by itself imply that the selected weights are close to $w^*$: different weights can yield nearly identical predictions and risks.

Worked Example: Validation-Fitted Weights Are Covered

Let $X$ be irrelevant, let $Y$ be Bernoulli with $P(Y=1)=0.4$, and use two fixed candidate predictors $f_1=0$ and $f_2=1$. Use squared loss $\ell(y,a)=(y-a)^2$, which lies in $[0,1]$ for $y,a\in[0,1]$. Write $a$ for the weight on $f_2$; the stacked prediction is $a$, with $0\leq a\leq1$.

Suppose the validation sample has outcomes $0,0,1$. Its empirical risk is $$ \widehat R_3(a)=\frac{2a^2+(1-a)^2}{3} =\frac{3a^2-2a+1}{3}. $$ Differentiating gives $\widehat R_3'(a)=(6a-2)/3$, so the empirical minimizer is $\hat a=1/3$, which depends on the validation outcomes. The population risk is $R(a)=0.4(1-a)^2+0.6a^2=0.4-0.8a+a^2$, minimized at $a^*=0.4$. Thus $$ R(\hat a)=0.4-0.8(1/3)+(1/3)^2=\frac{11}{45}\approx0.2444,\qquad R(a^*)=0.24, $$ and the excess risk is $11/45-0.24=1/225\approx0.0044$.

The weights were selected using the validation sample, but a uniform event over all $a\in[0,1]$ covers the selected $1/3$ just as it covers any fixed weight. Here the candidates themselves are fixed independently of validation data. For squared loss on $[0,1]$, the loss is $2$-Lipschitz in the prediction, since $|(y-a)^2-(y-b)^2|=|a-b||a+b-2y|\leq2|a-b|$.

Worked Example: Checking a Concentration Contribution

Suppose a conservative bound uses a concentration contribution $4\sqrt{A/(2n)}$, with $A=16.12$ and $n=1000$. Evaluate it, retaining enough precision to round correctly to four decimal places.

First calculate $2n=2000$, so $A/(2n)=16.12/2000=0.00806$. Then $\sqrt{0.00806}\approx0.0897775$, and multiplying the unrounded value by four gives $4\sqrt{0.00806}\approx0.3591099$. Rounded to four decimal places, the contribution is $0.3591$. Multiplying the intermediate value rounded prematurely to $0.0898$ gives $0.3592$; that is a conservative upward rounding, but it is not the correctly rounded value of the original expression.

Assumptions and a Common Pitfall

The conditional formulation matters. The candidate predictors may have been learned from training data: condition on that data, then require the validation observations to be independent and identically distributed and independent of the training data. The uniform argument does not require the fitted weights to be independent of validation data. This distinction is useful precisely because stacking weights are often chosen by minimizing validation empirical risk.

Incorrect reasoning: “The weights use the validation outcomes, so a validation-sample risk bound cannot apply to them.” This treats a pointwise bound as if it were the only available type of bound.
Correction: The theorem controls the supremum of the empirical-population discrepancy over the whole simplex on one event. Therefore it also controls any validation-dependent choice in that simplex.
Different issue: If the candidate predictors are also fitted using the same validation observations, they need not be fixed conditional on training data, and the proof above does not apply as stated. The grid-point Hoeffding argument relies on fixed candidates and independent validation observations.
Another mistake: A small optimization error $\eta$ alone does not guarantee good population risk. The empirical-to-population term must also be controlled.

The bound is only as useful as its assumptions and complexity term. A large candidate library or a fine grid can make the finite-grid bound loose, even though the oracle inequality remains valid. It is a guarantee relative to the candidate class and the chosen loss, not a guarantee that the class contains a predictor with small absolute risk.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

Why does a uniform risk bound over $\Delta_K$ cover weights selected using the validation observations?
In the finite-grid theorem, which assumption permits Hoeffding's inequality to be applied at a fixed grid point?
If the uniform discrepancy is at most $0.06$ and an empirical solution is within $0.02$ of the empirical minimum, what is the resulting oracle excess-risk bound?
For two candidates with predictions bounded in absolute value by $B$, why is $|f_w(x)-f_v(x)|\leq B\|w-v\|_1$?
What changes in the proof if the candidate predictors are fitted using the validation observations?