KKT Conditions for Convex Ensemble Weights

Why Constraints Change the Weighting Problem

A linear combination of predictors can reduce squared-error risk, but weights chosen without constraints need not form an average: some may be negative, and their sum may differ from one. Here the target is specifically a convex ensemble, whose weights are nonnegative and sum to one. These constraints make the optimization a quadratic problem on a simplex, and the Karush–Kuhn–Tucker (KKT) conditions describe precisely which members can receive positive weight.

Treat the candidate predictors as fixed functions $h_1,\ldots,h_K$ evaluated on a new observation $(X,Y)$. Assume $E[Y^2]<\infty$ and $E[h_j(X)^2]<\infty$ for every $j$, so all risks and cross-products below are finite. The risk is evaluated under the distribution of this new observation.

Definition: For member $j$, let $e_j=h_j(X)-Y$ be its prediction error, and define the error second-moment matrix $M$ by $M_{jk}=E[e_je_k]$. For weights $w=(w_1,\ldots,w_K)^T$, the convex ensemble risk is $$ R(w)=E\left[\left(\sum_{j=1}^K w_j h_j(X)-Y\right)^2\right]=w^TMw, $$ subject to $w_j\geq 0$ and $\sum_{j=1}^K w_j=1$.

The equality in the definition uses the sum-to-one constraint: $\sum_j w_jh_j(X)-Y=\sum_jw_j(h_j(X)-Y)$. The matrix $M$ is symmetric and positive semidefinite, since for every vector $a$, $$ a^TMa=E\left[\left(\sum_{j=1}^K a_je_j\right)^2\right]\geq 0. $$ Consequently, $R$ is a convex quadratic function. The feasible set, the simplex, is closed and bounded, and $R$ is continuous, so a risk-minimizing feasible weight vector exists.

The KKT Conditions on the Simplex

Write $\mathbf{1}$ for the $K$-vector of ones. The constraints are $1^Tw=1$ and $-w_j\leq 0$. With multiplier $\lambda$ for the equality constraint and multipliers $\nu_j$ for the inequalities, the Lagrangian is

\mathcal{L}(w,\lambda,\nu)=w^TMw+\lambda(1^Tw-1)-\nu^Tw,\qquad \nu_j\geq 0.

Since $M$ is symmetric, the gradient of $w^TMw$ is $2Mw$. The KKT conditions are stationarity, primal feasibility, dual feasibility, and complementary slackness:

2Mw+\lambda\mathbf{1}-\nu=0,\qquad 1^Tw=1,\quad w_j\geq 0,\qquad \nu_j\geq 0,\quad \nu_jw_j=0\quad (j=1,\ldots,K).

The signs matter. A positive weight forces its inequality multiplier to be zero; a zero weight may have a positive multiplier. For this convex problem, these conditions are both necessary and sufficient for global optimality.

Theorem: A feasible vector $w$ minimizes $R(w)=w^TMw$ over the simplex if and only if there is a scalar $\lambda$ and a vector $\nu$ satisfying the KKT conditions above. Equivalently, if $A=\{j:w_j>0\}$, then $$ (Mw)_j=R(w)\quad\text{for }j\in A,\qquad (Mw)_j\geq R(w)\quad\text{for }j\notin A. $$

Proof. Let $g=2Mw$, the gradient of $R$. First suppose $w$ is a minimizer. There is at least one active coordinate because the weights sum to one. For any two active indices $i,j$, both directions $e_i-e_j$ and $e_j-e_i$ are feasible for sufficiently small positive steps: both coordinates are positive, and their sum is unchanged. The directional derivative at a minimum cannot be negative in either direction. Thus $g_i-g_j\geq0$ and $g_j-g_i\geq0$, so $g_i=g_j$. Denote their common value by $c$.

For an inactive index $k$ and any active index $i$, the direction $e_k-e_i$ is feasible for a sufficiently small positive step: it adds weight to $k$ and removes the same amount from $i$. Its directional derivative must be nonnegative, giving $g_k-g_i\geq0$, or $g_k\geq c$. Set $\lambda=-c$; set $\nu_i=0$ for active indices and $\nu_k=g_k-c$ for inactive indices. Then $\nu\geq0$, $\nu_jw_j=0$, and $g+\lambda\mathbf{1}-\nu=0$. This proves necessity.

For sufficiency, suppose the KKT conditions hold and $v$ is any other feasible vector. The exact quadratic expansion gives

$$ R(v)-R(w)=2(Mw)^T(v-w)+(v-w)^TM(v-w). $$

By stationarity, $2Mw=-\lambda\mathbf{1}+\nu$. Since both weight vectors sum to one, $\mathbf{1}^T(v-w)=0$; and since $\nu_jw_j=0$, $\nu^T(v-w)=\nu^Tv\geq0$. The final inequality follows from $\nu\geq0$ and $v\geq0$. The quadratic remainder is nonnegative because $M$ is positive semidefinite. Therefore $R(v)-R(w)\geq0$ for every feasible $v$, proving sufficiency.

To obtain the equivalent risk-threshold form, multiply the stationarity equation by $w^T$. Complementary slackness gives $\nu^Tw=0$, while $1^Tw=1$, so $2R(w)+\lambda=0$. For an active coordinate, stationarity gives $2(Mw)_j=-\lambda=2R(w)$. For an inactive coordinate, $\nu_j=2(Mw)_j+\lambda\geq0$, hence $(Mw)_j\geq R(w)$. This completes the proof. $\square$

Worked Examples

Worked Example: Two Members Both Receive Positive Weight

Let $U,V$ be independent random variables taking values $1$ and $-1$ with probability $1/2$ each. Suppose the two prediction errors are $e_1=2U$ and $e_2=\tfrac12U+\tfrac{\sqrt{7}}{2}V$. Then $E[e_1^2]=4$, $E[e_2^2]=\tfrac14+\tfrac74=2$, and $E[e_1e_2]=1$. Thus

M=\begin{pmatrix}4&1\\1&2\end{pmatrix}.

Write $w_1=t$, $w_2=1-t$, where $0\leq t\leq1$. The risk is $$ R(t)=4t^2+2(1-t)^2+2t(1-t)=4t^2-2t+2. $$ Its derivative is $8t-2$, which vanishes at $t=\tfrac14$, inside the feasible interval. The resulting weights are $w=(\tfrac14,\tfrac34)^T$. Directly,

Mw=\begin{pmatrix}4(\tfrac14)+\tfrac34\\[2pt]\tfrac14+2(\tfrac34)\end{pmatrix} =\begin{pmatrix}\tfrac74\\[2pt]\tfrac74\end{pmatrix}, \qquad R(w)=w^TMw=\tfrac74.

Both members are active, and their coordinates in $Mw$ equal the ensemble risk. The KKT conditions hold with $\lambda=-\tfrac72$ and $\nu=(0,0)^T$. The risk is strictly convex along the feasible line here, so this minimizer is unique.

Worked Example: A Member Has Zero Optimal Weight

Let $U,V,W$ be independent Rademacher variables, each equally likely to be $1$ or $-1$, and take $e_1=\sqrt{2}U$, $e_2=\sqrt{2}V$, and $e_3=\sqrt{2}U+\sqrt{2}V+W$. Their second-moment matrix is

M=\begin{pmatrix}2&0&2\\0&2&2\\2&2&5\end{pmatrix}.

Consider $w=(\tfrac12,\tfrac12,0)^T$. Then

Mw=\begin{pmatrix}1\\1\\2\end{pmatrix}, \qquad R(w)=w^TMw=1.

The first two members are active and both satisfy $(Mw)_j=R(w)$. The third is inactive and satisfies $(Mw)_3=2>1=R(w)$. In multiplier form, $\lambda=-2$ and $\nu=(0,0,2)^T$, so stationarity, dual feasibility, and complementary slackness all hold. The inactive multiplier records a strict first-order cost to introducing this member: along $w(\epsilon)=(1-\epsilon)w+\epsilon(0,0,1)^T$, the derivative of risk at $\epsilon=0$ is $2((Mw)_3-R(w))=2$.

Worked Example: Zero Weight Does Not Always Mean Strictly Worse

Suppose all three members have the same error $e_1=e_2=e_3=U$, where $U$ is equally likely to be $1$ or $-1$. Then $M$ is the $3$-by-$3$ matrix of ones. For every feasible $w$, the ensemble error is $(w_1+w_2+w_3)U=U$, so $R(w)=1$.

At the vertex $w=(1,0,0)^T$, $Mw=(1,1,1)^T$ and $R(w)=1$. The KKT conditions hold with $\lambda=-2$ and $\nu=(0,0,0)^T$; the inactive coordinates meet the risk threshold with equality. In fact, every simplex weight vector has the same risk. Thus zero weight alone does not establish that a member worsens the ensemble: the inactive inequality can be an equality, and multiple optimal weight vectors can exist.

Interpreting the Conditions and Avoiding a Common Mistake

The quantity $(Mw)_j=E[e_j\sum_k w_ke_k]$ measures how the error of member $j$ aligns with the current ensemble error. It is half the derivative of risk with respect to $w_j$ before imposing the sum constraint. The KKT result says that positive-weight members must have equal alignment with the ensemble error. An excluded member cannot have a smaller alignment: otherwise, shifting a small amount of weight from an active member to it would reduce risk.

More explicitly, for an inactive member $j$ and an active member $i$, the feasible perturbation $w(\epsilon)=w+\epsilon(e_j-e_i)$ has derivative

\left.\frac{d}{d\epsilon}R(w(\epsilon))\right|_{\epsilon=0} =2\big((Mw)_j-(Mw)_i\big) =2\big((Mw)_j-R(w)\big)\geq0.

Common mistake: It is tempting to solve the unconstrained linear equations for the weights, set any negative answers to zero, and renormalize what remains. That procedure does not generally enforce the KKT equalities among the retained members or the required inequalities for excluded ones. The correction is to check the constrained optimality conditions on the resulting simplex vector: every positive-weight coordinate of $Mw$ must equal $R(w)$, and every zero-weight coordinate must be at least $R(w)$. Correlations between errors matter, so an individual member's error variance alone does not determine whether it belongs in the optimal convex ensemble.

These conditions are useful both for computing weights and for understanding the answer. If a proposed active set is known, the equalities for its members, together with weights summing to one, give equations to solve; the inactive inequalities then check whether that set is consistent with optimality. If the quadratic has flat directions on the simplex, the optimum need not be unique, as the identical-error example shows. In all cases, the KKT conditions characterize global risk minimizers, not merely stationary points.

Check Your Understanding

Use the simplex constraints and the risk-threshold form of the KKT conditions to answer these questions.

Why is the error second-moment matrix positive semidefinite, even if some off-diagonal entries are negative?
At a minimizer, what equality must hold for every member with positive weight?
What inequality must an inactive member satisfy, and what feasible perturbation explains it?
Can an inactive member have the same value of $(Mw)_j$ as the ensemble risk? What does that imply about interpreting its zero weight?
Why is the KKT condition sufficient for global optimality in this problem?

KKT Conditions for Convex Ensemble Weights

What You'll Learn