Learning Kernels Using Local Rademacher Complexity

Corinna Cortes, Marius Kloft, Mehryar MohriNeurIPS 2013 · OpenReview

Introduction

In kernel-based machine learning, such as Support Vector Machines (SVMs), the choice of the kernel function is critical—it defines the feature space and the similarity measure between data points. Multiple Kernel Learning (MKL) was developed to automate this process, allowing algorithms to choose the optimal combination of kernels from a provided set.

Traditionally, MKL algorithms are designed based on global Rademacher complexity, a theoretical measure of how much a hypothesis class can "fit" random noise. To prevent overfitting, standard MKL typically constrains the "trace" (the sum of all eigenvalues) of the combined kernel matrix. However, global complexity is a "worst-case" measure. It fails to account for the fact that learning algorithms usually select hypotheses that perform much better than average. This discrepancy leads to "loose" theoretical bounds and sub-optimal kernel combinations in practice.

This paper introduces a more refined approach to automate kernel selection by leveraging local Rademacher complexity. By focusing on the "tail sum" of a kernel's eigenvalues rather than its total trace, the authors develop two new algorithms that achieve faster convergence rates and superior accuracy on challenging biological classification tasks.

Methods: The Power of the "Tail Sum"

The authors propose using local Rademacher complexity, which evaluates the complexity of only the "good" hypotheses (those with low error). Theoretically, this leads to much tighter generalization bounds and faster convergence rates, approaching $O(1/n)$ instead of the usual $O(1/\sqrt{n})$.

The key technical insight is that local Rademacher complexity is determined by the tail sum of the eigenvalues of the kernel matrix, rather than the sum of all eigenvalues. Kernels with a few dominant eigenvalues and a quickly decaying "tail" are often more favorable for generalization.

Log tail sum of eigenvalues for different kernels in the TSS dataset.

Based on this insight, the authors propose two new hypothesis classes for kernel learning:

  1. The DC Approach ($H_1$): A hypothesis class where the tail sum of the combined kernel is directly constrained. This creates a non-convex optimization problem, which the authors solve using Difference of Convex (DC) programming. The solution involves an iterative process that alternates between training an SVM and performing an eigenvalue decomposition.
  2. The Convex Approach ($H_2$): A convex relaxation of $H_1$. This version is significantly easier to implement because it can be solved by simply re-normalizing the base kernels and plugging them into existing, highly optimized MKL solvers (like $\ell_1$ or $\ell_2$ MKL).

Key Results and Feature Selection

The authors evaluated their algorithms on several bioinformatics datasets, including a Transcription Start Site (TSS) detection task (using 5 specialized kernels) and multi-class protein sequence data (using up to 69 biologically motivated sequence kernels).

Superior Accuracy and Nuanced Selection

A major limitation of standard $\ell_1$ MKL is that it often forces "sparsity," entirely discarding many kernels. The local Rademacher approach is more nuanced: it retains kernels that have high predictive power even if they appear "complex" by global standards, provided their eigenvalue tail is well-behaved.

In the TSS detection task, both the convex (conv) and DC-programming (dc) versions consistently outperformed standard $\ell_1$ MKL, $\ell_2$ MKL, and simple uniform combinations across different sample sizes.

Kernel weights assigned by different MKL algorithms on the TSS dataset.

Crucially, standard MKL discarded the "1st Exon" kernel because its global complexity appeared too high. However, the new algorithms recognized its high predictive value (85.8% AUC on its own) and assigned it significant weight, leading to better overall predictive performance.

Multi-class Gains

The benefits extended to complex multi-class problems. On the difficult proteinFold dataset (which contains 27 classes), the conv algorithm achieved 59.6% accuracy, representing a significant jump over the 57.2% achieved by both uniform combinations and standard MKL.

Limitations and Future Work

While the proposed methods successfully translate a sophisticated theoretical concept into concrete optimization constraints, there are a few limitations:

  • Computational Overhead: The DC-programming approach requires an eigenvalue decomposition of the kernel matrix in every iteration. Although the authors provide a method to speed this up by computing only the top eigenvalues, it remains more computationally demanding than standard MKL.
  • Parameter Tuning: The algorithms introduce a new hyperparameter $\theta$ (the "cut-off point" for the tail sum). While this can be tuned via cross-validation, it adds another dimension to the model selection process.
  • Uncorrelated Kernels: Some of the strongest theoretical guarantees in the paper assume the kernels are uncorrelated. Extending these tight bounds to highly correlated kernel sets remains an area for further theoretical refinement.

Summary updated

Abstract

We use the notion of local Rademacher complexity to design new algorithms for learning kernels. Our algorithms thereby benefit from the sharper learning bounds based on that notion which, under certain general conditions, guarantee a faster convergence rate. We devise two new learning kernel algorithms: one based on a convex optimization problem for which we give an efficient solution using existing learning kernel techniques, and another one that can be formulated as a DC-programming problem for which we describe a solution in detail. We also report the results of experiments with both algorithms in both binary and multi-class classification tasks.
BibTeX
@inproceedings{cortes2013learning,
  author = {Corinna Cortes and Marius Kloft and Mehryar Mohri},
  title = {{Learning Kernels Using Local Rademacher Complexity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=HyETluWd-r},
}
Figure