Introduction
This paper provides significantly tighter theoretical guarantees for Multiple Kernel Learning (MKL). It proves that the risk of overfitting grows much slower than previously thought as you add more base kernels to a model. Specifically, for sparse ($L_1$-regularized) combinations, the generalization error only increases with the square root of the logarithm of the number of kernels ($\sqrt{\log p}$). This means practitioners can safely use thousands of kernels even with limited data without suffering from severe overfitting.
The Overfitting Problem in MKL
In machine learning, "kernel methods" (like Support Vector Machines) rely on a kernel function to define the similarity between data points. Choosing the right kernel is often a manual, trial-and-error process. Learning Kernels (or MKL) automates this by allowing an algorithm to learn an optimal combination of many "base kernels."
The primary theoretical worry with MKL has been the "curse of dimensionality": if an algorithm is given too many kernels to choose from, it might "memorize" the noise in the training data rather than learning a generalizable pattern. Previous mathematical bounds on this error were either too loose to be useful or suggested that the error grew rapidly as the number of kernels ($p$) increased. This paper aims to find the tightest possible mathematical limits to demonstrate that MKL is fundamentally more robust than older theories suggested.
Theoretical Framework
The authors utilize Rademacher complexity, a modern tool in statistical learning theory that measures how well a class of functions can fit random noise. Their primary technical contribution is a novel combinatorial analysis of kernel matrices.
Key methodological steps include:
- Khintchine-Kahane type inequality: The authors derive a new technical lemma that bounds the expected power of a random quadratic form involving kernel matrices.
- $L_q$ Regularization Analysis: They analyze different ways to constrain the kernel weights, specifically contrasting $L_1$ regularization (which encourages sparse combinations where most kernels get zero weight) and $L_2$ regularization (which spreads weights more evenly).
- Tightness Proofs: Beyond providing an upper bound, they use VC-dimension arguments to show that their $\sqrt{\log p}$ dependency is a "lower bound" as well, meaning the theoretical limit cannot be improved further.
Key Findings and Empirical Validation
The most striking insight from the paper is the power of logarithmic scaling. For $L_1$ regularization, the generalization error is bounded by $O\left(\sqrt{\frac{\log p}{m}}\right)$. In practical terms, if you scale your model from 10 kernels to 1,000, the complexity only increases by a factor of about $\sqrt{3} \approx 1.73$, rather than 100.
Conversely, $L_2$ regularization is shown to be much more sensitive to high-dimensional kernel sets, with an established bound of $O\left(\frac{p^{1/4}}{\sqrt{m}}\right)$ for non-negative combinations.
Previous bounds often featured terms where the number of kernels multiplied other complexity factors, rendering them "uninformative" (greater than 1) even for realistic sample sizes. As shown above, the new bounds move toward additive or logarithmic dependencies, dropping below the critical threshold of 1 much earlier than prior benchmarks (e.g., Srebro & Ben-David, 2006).
To validate these findings, the authors tested their bounds on the classic MNIST handwritten digit dataset, generating a large number of rank-1 base kernels to observe how generalization error behaves as $p$ grows from 200 to 800.
The experimental results closely match the theory. The actual test error follows the "mild" upward curve predicted by the logarithmic bound, whereas older theories would have predicted a much sharper spike in error. Furthermore, the techniques used here actually improve the constants for standard linear classification bounds, outperforming contemporary methods that relied on "strong convexity" arguments.
Limitations and Future Directions
Despite the strong theoretical results, the authors note a few limitations:
- The "MKL Paradox": There remains a gap between theory and practice. While the theory dictates that learning kernels should work exceptionally well without overfitting, MKL often provides only modest empirical improvements over a simple average of kernels in real-world tasks.
- Kernel Choice: The bounds assume the base kernels are fixed and do not account for the complexity of "learning" or tuning the base kernels themselves (e.g., optimizing the bandwidth of a Gaussian kernel).
- Optimization: The paper focuses on the existence of a good generalization bound, not the computational efficiency of the algorithms used to find the optimal weights.
A suggested next step for the field is investigating why this theoretical optimism hasn't consistently translated into massive empirical gains, potentially by examining the "alignment" of kernels or the specific properties of underlying data distributions.
Summary updated