In machine learning, we often represent data through "kernels"—functions that measure the similarity between two points. Since different kernels capture different facets of data (like color versus texture in an image), Multiple Kernel Learning (MKL) was developed to automatically learn the best combination of these representations.
For years, the dominant philosophy in MKL was sparsity. Researchers used $\ell_1$-norm regularization to force the model to pick just one or two "best" kernels, discarding the rest. The intuition was simple: a sparse model is easier to interpret and faster to compute. However, a growing body of research has shown that this "winner-takes-all" approach often leaves significant accuracy on the table.
The Failure of Sparse Selection
The problem with aggressive sparsity is that real-world information is rarely concentrated in a single feature. As Alexander Binder and Marius Kloft observed in Insights from Classifying Visual Concepts with Multiple Kernel Learning, sparse MKL often fails to outperform a simple unweighted average of kernels.
When kernels are non-redundant—meaning they each provide a unique, subtle signal—forcing most weights to zero discards useful information. Corinna Cortes and Mehryar Mohri argue in L2 Regularization for Learning Kernels that dense regularization (using the $\ell_2$-norm) is more robust because it preserves contributions from all available kernels, preventing the model from overfitting to a single "lucky" feature.
Bridging the Gap with Mixed Norms
To solve this, researchers moved toward mixed-norm regularization, which allows for a tunable balance between sparsity and density. The most common tool for this is the $\ell_p$-norm, where $p$ is a parameter between 1 (purely sparse) and $\infty$ (purely dense).
As Zenglin Xu demonstrates in Simple and Efficient Multiple Kernel Learning by Group Lasso, using $p > 1$ allows the model to retain a broader set of features. This is particularly effective in complex domains like protein fold recognition, where Kaizhu Huang showed that integrating heterogeneous data sources through non-sparse weighting leads to significant accuracy gains (Enhanced protein fold recognition through a novel data integration approach).
Another powerful approach is Elastic-net regularization, which combines $\ell_1$ and $\ell_2$ penalties. Taiji Suzuki and Masashi Sugiyama proved that while $\ell_1$ is optimal for raw feature selection, the Elastic-net is superior when the underlying "ground truth" function is smooth (Fast Learning Rate of Multiple Kernel Learning: Trade-Off between Sparsity and Smoothness).
Dual Penalties for Complex Data
The modern frontier of this research applies these mixed norms to "functional data"—data that exists as continuous curves or surfaces rather than static points. Daren Wang and Rebecca Willett describe a dual-penalty structure in Functional Linear Regression with Mixed Predictors.
In this framework, the model uses:
- A smoothness penalty (like a Reproducing Kernel Hilbert Space norm) to ensure the learned curves don't fluctuate erratically.
- A sparsity penalty (like Group Lasso) to select which high-dimensional features actually matter.
This combination allows models to handle "mixed" data—like a patient's continuous heart rate monitor combined with their static medical history—without being overwhelmed by noise.
Why It Works: Theoretical Intuition
The success of non-sparse MKL isn't just empirical; it has deep theoretical roots. Gilles Blanchard used local Rademacher complexity to prove that non-sparse kernel combinations can achieve faster convergence rates than sparse ones in many practical scenarios (The Local Rademacher Complexity of Lp-Norm Multiple Kernel Learning).
Essentially, if your candidate kernels have varying levels of complexity, a rigid $\ell_1$ penalty might discard a complex but highly informative kernel in favor of a simpler, less useful one. Mixed norms provide the mathematical flexibility to weight kernels based on their actual contribution to the task, rather than their mathematical simplicity.
By moving from "selection" to "integration," mixed-norm MKL allows researchers to build models that are both theoretically sound and robust enough for the messy, distributed nature of real-world data.