Quadratic Optimization for Model and Kernel Combinations

41 concepts31 papers1 proposal

When building machine learning systems, we rarely rely on a single isolated model or feature space. Instead, we frequently find ourselves combining multiple perspectives: ensembling diverse classifiers, integrating multi-view data, or fusing a dictionary of different kernel functions.

The fundamental challenge in these scenarios is determining how much to trust each component. If we try to select the single best component discretely, we face an NP-hard combinatorial search. If we use greedy heuristics—like adding one model at a time—we often miss the globally optimal combination.

A powerful alternative approach has emerged across various subfields: transforming the search for optimal combination weights into a convex quadratic optimization problem (such as a Quadratic Program (QP) or a Second-Order Cone Program (SOCP)). By framing the objective function so that it depends only linearly and quadratically on the weights, we unlock a clean mathematical landscape. These formulations guarantee a single global optimum and allow us to leverage highly efficient, scalable solvers.

The Geometry of Combination: From Selection to Quadratic Blending

To understand why quadratic optimization is such a natural fit for model ensembling, consider what happens when we blend predictions. We do not merely care about the individual accuracy of each model; we care about how their errors correlate.

When we combine probabilistic models or classifiers, the total variance or disagreement introduces cross-product terms between the weights ($w_i w_j$). This interaction inherently creates a quadratic surface.

For instance, in the context of combining probabilistic models, Tom Heskes demonstrates in Selecting Weighting Factors in Logarithmic Opinion Pools that a second-order approximation of the ensemble's ambiguity term transforms the weight selection task into a clean QP. This quadratic term acts as a mathematically grounded mechanism to balance individual expert accuracy against ensemble diversity.

A similar geometric intuition applies to boosting and margin optimization. Instead of greedily minimizing an exponential loss, we can optimize the entire distribution of the margins (the distances between data points and the decision boundary). Chunhua Shen et al. show in Boosting through Optimization of Margin Distributions that the selection and weighting of base learners can be formulated as a convex QP. By directly optimizing second-order margin statistics—maximizing the average margin while minimizing its variance—the quadratic formulation provides a far more stable objective than traditional linear programming.

Even in modern tabular boosting frameworks, incorporating a quadratic regularization term into weight updates enhances numerical stability, allowing ensemble weights to be determined in a single direct step rather than through complex iterative solvers, as shown by Fabian Akkerman et al. in Boosting Revisited: Benchmarking and Advancing LP-Based Ensemble Methods (Accepted by TMLR 2025).

Collapsing Semidefinite Programs into Quadratic Programs

The shift toward quadratic formulations has been particularly transformative for Multiple Kernel Learning (MKL). A kernel function defines a non-linear similarity space for algorithms like Support Vector Machines (SVMs). Rather than manually tuning a single kernel, we can express the ideal kernel as a linear combination of base kernels: $K_{\mu} = \sum \mu_i K_i$.

Historically, learning the matrix $K_{\mu}$ required Semidefinite Programming (SDP) because the resulting matrix must be constrained to be positive semi-definite (PSD). However, general SDP solvers are computationally expensive, scaling poorly to large datasets.

The key insight that unlocked practical kernel learning was that we can bypass the semi-definite cone constraint entirely through clever problem framing.

In their seminal work, Gert Lanckriet et al. demonstrated in Learning the Kernel Matrix with Semi-Definite Programming that if we restrict the kernel combination weights $\mu_i$ to be non-negative, the optimization problem collapses from a general SDP into a quadratically constrained quadratic program (QCQP) or a standard QP. Because a non-negative linear combination of PSD matrices is automatically PSD, the expensive matrix-cone constraint disappears, replaced by simple element-wise non-negativity constraints on the weights.

General SDP Formulation (Expensive)
  Minimize over Matrix K
  Subject to: K is Positive Semi-Definite (Cone Constraint)
         ▼
Non-Negative Weight Restriction (Lanckriet et al.)
         ▼
Standard QP Formulation (Efficient)
  Minimize over Vector μ
  Subject to: μ ≥ 0 (Simple Linear Constraints)

This reduction makes automated kernel selection practical. For example, Corinna Cortes et al. show in Algorithms for Learning Kernels Based on Centered Alignment that maximizing the centered alignment score between a combined kernel and target labels reduces to a simple, highly scalable QP.

Similarly, when applying kernels to spectral clustering, Zhenguo Li et al. demonstrate in Constrained clustering by spectral kernel learning that by fixing the spectral basis and optimizing only the associated eigenvalues, the problem drops from an SDP to a convex QP, drastically reducing processing time.

When a full reduction to a QP is not possible, the problem can often still be mapped to a Second-Order Cone Program (SOCP), which sits between QPs and SDPs in complexity. James Kwok et al. proved in Efficient Hyperkernel Learning Using Second-Order Cone Programming that utilizing Lagrangian duality to convert hyperbolic constraints into second-order cone constraints yields massive speedups while maintaining the exact optimal solution.

Direct Optimization of Generalization Bounds

Another reason why quadratic weight optimization works so well is its alignment with statistical learning theory. In many cases, minimizing empirical training error directly is a bad idea—it leads to overfitting and results in non-convex, discontinuous step functions that are difficult to optimize.

Instead, we can use quadratic programming to directly optimize theoretical generalization bounds.

Consider a majority vote ensemble. Jean-Francis Roy et al. in From PAC-Bayes Bounds to Quadratic Programs for Majority Votes and Pascal Germain et al. in Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm leveraged PAC-Bayesian theory to derive the "C-bound," a risk bound that explicitly accounts for the disagreement between voters.

The authors uncovered a beautiful optimization trick: if you fix the first moment of the ensemble's margin (its average performance) to a constant hyperparameter, minimizing the risk bound reduces to minimizing the second moment of the margin. Because the second moment represents variance, it is inherently quadratic with respect to the voter weights. This mathematical transformation turns the highly non-convex task of training a majority vote classifier into a standard, easily solvable convex QP.

$$\arg\min_{\mathbf{w}} \mathbf{w}^T \mathbf{M} \mathbf{w} \quad \text{subject to} \quad \mathbf{w}^T \boldsymbol{\mu} = c, \ \mathbf{w} \ge 0$$

Where $\mathbf{M}$ is the matrix of pairwise voter correlations, $\boldsymbol{\mu}$ is the vector of mean voter margins, and $c$ is a fixed performance target.

A Unifying Tool Across Paradigms

The strategy of framing weight learning as a convex quadratic problem extends far beyond ensembling and kernel learning. It serves as a general-purpose tool for data integration across machine learning:

  • Mixture Proportion Estimation: When trying to find the weights of individual components within a mixed dataset, Tongliang Liu shows in An Efficient and Provable Approach for Mixture Proportion Estimation Using Linear Independence Assumption that by minimizing the squared Maximum Mean Discrepancy (MMD) between the embedded mixture and the weighted sum of component embeddings, the task becomes a single convex QP, bypassing the need for iterative greedy searches.
  • Causal Inference: In observational studies, finding balanced weights for covariates across treatment groups can be framed as a QP. Kwangho Kim et al. demonstrate in A kernel balancing approach that scales to big data that this formulation can scale to massive datasets by using the Operator Splitting Quadratic Program (OSQP) solver, which implements the Alternating Direction Method of Multipliers (ADMM).
  • Multi-View Clustering: When data is described by multiple heterogeneous feature sets (views), Linlin Zong et al. show in Weighted Multi-View Spectral Clustering Based on Spectral Perturbation that view-weighting can be solved via standard QP solvers, ensuring that adaptive multi-view clustering remains stable and computationally feasible.
  • Safe Semi-Supervised Learning: Semi-supervised learning can occasionally degrade performance if unlabeled data is noisy. To mitigate this, Yu-Feng Li et al. design a framework in Learning Safe Prediction for Semi-Supervised Regression that optimizes model weights using a convex QP, mathematically guaranteeing that the final ensemble never performs worse than a simple supervised baseline.

Ultimately, quadratic weight optimization works because it strikes a perfect compromise in machine learning design. It is expressive enough to capture the complex, second-order interactions between models, views, or kernels, yet simple enough to preserve the global convergence guarantees and rapid execution speeds of convex optimization.

Key Foundational Work

Learning the Kernel Matrix with Semi-Definite Programming (2002) — contributed 2 concept elements to this direction.
Selecting Weighting Factors in Logarithmic Opinion Pools (1997) — contributed 2 concept elements to this direction.
Optimizing Kernel Alignment over Combinations of Kernel (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_weight_optimization_53fb7363,
  title = {quadratic weight optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-weight-optimization/rdr_53fb7363e31c4fe7ba701cf2d9eb81fd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_quadratic_weight_optimization_53fb7363_v1,
  title = {quadratic weight optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-weight-optimization/rdr_53fb7363e31c4fe7ba701cf2d9eb81fd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake