Least-Squares Fitting Of Simplex Weights

From a Dictionary to a Fitted Mixture

Suppose a finite dictionary supplies \(M\) predictors \(g_1,\ldots,g_M\), each mapping an input \(x\) to a real-valued prediction. Instead of selecting one predictor, we can form a weighted prediction. Requiring the weights to be nonnegative and sum to one makes the prediction a convex combination of the dictionary outputs. Least-squares fitting chooses the weights that minimize squared error on the observed sample.

This is a convex optimization problem, but the weights are not generally obtained by minimizing each predictor’s error separately. The predictors interact: a candidate that is imperfect on its own may help when combined with another candidate. The simplex constraint also matters, since it rules out negative weights and weights whose sum differs from one.

The empirical least-squares weights are any minimizer \(\hat\lambda\in\arg\min_{\lambda\in\Delta_M}\hat R_n(\lambda)\). Since the simplex is compact and the empirical objective is continuous, a minimizer exists. It need not be unique: different weights can give identical fitted values on the observed inputs.

The Quadratic Program and Its Optimality Conditions

Write \(g_{ij}=g_j(X_i)\). Expanding the squared residuals gives a convenient matrix form. Define \(A\) as the \(M\times M\) matrix with entries \(A_{jk}=n^{-1}\sum_{i=1}^n g_{ij}g_{ik}\), define \(b_j=n^{-1}\sum_{i=1}^nY_i g_{ij}\), and let \(c=n^{-1}\sum_{i=1}^nY_i^2\). Then

The matrix \(A\) is positive semidefinite: for every \(v\in\mathbb R^M\), \(v^\mathsf{T}Av=n^{-1}\sum_i(\sum_jv_jg_{ij})^2\geq 0\). Thus the objective is convex. It may be strictly convex if \(A\) is positive definite, in which case the minimizer over the convex simplex is unique. Positive definiteness is sufficient, not necessary, for uniqueness.

The gradient coordinate for weight \(j\) has a direct residual interpretation:

At an optimum, gradients for predictors receiving positive weight must agree. A predictor receiving zero weight cannot have a smaller gradient, since shifting a little weight to it would then decrease the objective.

Proof. For a differentiable convex function \(q\) on a convex set \(C\), a point \(\lambda\in C\) minimizes \(q\) if and only if \(\nabla q(\lambda)^\mathsf{T}(u-\lambda)\geq 0\) for every \(u\in C\). Necessity follows by considering the right derivative at zero of \(q(\lambda+t(u-\lambda))\) for \(0\leq t\leq1\). For sufficiency, convexity gives \(q(u)\geq q(\lambda)+\nabla q(\lambda)^\mathsf{T}(u-\lambda)\geq q(\lambda)\).

Apply this criterion to the simplex. Taking \(u\) to be the vertex with all its weight on coordinate \(j\) shows that the criterion is \(\nabla_j q(\lambda)\geq\sum_k\lambda_k\nabla_k q(\lambda)\) for every \(j\). The weighted average on the right is therefore the minimum gradient coordinate. Every coordinate with positive weight must attain that minimum: otherwise the weighted average would exceed the minimum, contradicting the inequality for a minimum-gradient coordinate. Conversely, if all positive-weight coordinates have gradient \(\kappa\) and all other coordinates have gradient at least \(\kappa\), then \(\sum_k\lambda_k\nabla_k q(\lambda)=\kappa\), so the criterion holds. The residual-correlation statement follows from the displayed gradient formula. \(\square\)

Comparing Empirical Fit with the Population Oracle

The best simplex-weighted predictor for the target distribution is a population oracle \(\lambda^*\in\arg\min_{\lambda\in\Delta_M}R(\lambda)\). An empirical minimizer need not equal this oracle. A useful comparison follows directly from empirical optimality: if \(D_n=\sup_{\lambda\in\Delta_M}|\hat R_n(\lambda)-R(\lambda)|\), then

The middle inequality is the definition of empirical minimization; the other two follow from the definition of \(D_n\). This deterministic inequality separates fitting from generalization: the empirical optimizer compares well with the population oracle whenever the empirical and population risks are uniformly close over the simplex.

Proof. For any \(\lambda,\mu\in\Delta_M\), the bounds on the responses and predictors give \(|g_\lambda(X)|\leq B\) and \(|g_\lambda(X)-g_\mu(X)|\leq B\|\lambda-\mu\|_1\). Factoring a difference of squares therefore yields

The same bound holds for the difference of population risks and for the difference of empirical risks. Hence the change in \(\hat R_n-R\) between \(\lambda\) and \(\mu\) is at most \(8B^2\|\lambda-\mu\|_1\).

For \(0<\delta<1\), the simplex has a finite \(\delta\)-net in the \(\ell_1\) norm with at most \((1+2/\delta)^M\) points. To see this, take a maximal set of points in the simplex separated by more than \(\delta\). The radius-\(\delta/2\) \(\ell_1\) balls around them are disjoint and lie within the radius-\(1+\delta/2\) ball centered at zero, since every simplex point has \(\ell_1\) norm one. Comparing volumes bounds the number of points by \((1+2/\delta)^M\); maximality makes the set a \(\delta\)-net.

At each fixed net point, the squared loss lies in \([0,4B^2]\). Hoeffding’s inequality and a union bound show that the probability that any net-point deviation exceeds \(t>0\) is at most \(2(1+2/\delta)^M\exp(-nt^2/(8B^4))\). If no such deviation occurs, the Lipschitz bound extends the deviation from the net to the entire simplex, giving

For fixed \(\delta\) and \(t\), the right side tends to zero as \(n\) grows. Given any target deviation \(\varepsilon>0\), first choose \(\delta\) so that \(8B^2\delta<\varepsilon/2\), then choose \(t<\varepsilon/2\). The bound proves \(D_n\xrightarrow{p}0\). Substitution into the deterministic oracle inequality proves the population-risk comparison. \(\square\)

Interpretation and a Common Pitfall

Simplex-constrained least squares offers a principled way to use several predictors at once while keeping the resulting prediction within their convex hull. The KKT conditions describe which candidates can receive weight at an optimum, and the population comparison explains what additional ingredient supports a generalization claim: control of the risk difference over all allowed weights.

• Pitfall: treating the smallest training error as a population guarantee. The one-observation example has zero empirical error but population risk above the oracle’s. Empirical optimality alone gives only the comparison in empirical risk; a population claim also needs control of \(D_n\), or another valid generalization argument.
• Pitfall: assuming the fitted weights are always unique. Convexity guarantees that the set of minimizers is convex, not that it contains only one point. Predictors that agree on the observed inputs can make different weights empirically indistinguishable.
• Pitfall: ignoring the simplex constraint when interpreting weights. The KKT conditions include boundary cases. A zero-weight predictor need not have the same residual correlation as predictors with positive weight; its correlation must be no larger.