A DC-programming algorithm for kernel selection

Andreas Argyriou, Raphael Hauser, Charles A. Micchelli, Massimiliano PontilICML 2006 · DOI

Introduction

This paper introduces a powerful new framework for "learning the kernel" in machine learning models. Rather than searching through a small, pre-defined set of kernels, the authors propose a method to search through an infinite, continuously parameterized family of kernels. By formulating the kernel selection problem as a DC (Difference of Convex functions) program, the authors provide an efficient greedy algorithm that outperforms traditional grid-search methods in both accuracy and computational flexibility.

The Challenge of Kernel Selection

In kernel-based machine learning (such as Support Vector Machines), the choice of the "kernel"—the function that defines similarity between data points—is often the deciding factor between a model that succeeds and one that fails. Traditionally, practitioners either pick a single kernel (like a Gaussian with a specific variance $\sigma$) or combine a small, finite set of pre-chosen kernels.

The problem is that choosing this finite set is often arbitrary. If a grid of variances is too coarse, the optimal setting might be missed; if it is too fine, the computational cost becomes overwhelming. The authors tackle the challenge of searching over a continuous range of parameters (e.g., any $\sigma$ in an interval) or even complex structures like full covariance matrices. This continuous search leads to a non-convex optimization problem that is notoriously difficult to solve globally.

Methodology

The authors build on the idea of minimizing a convex regularization functional over the convex hull of a family of basic kernels. Their approach consists of two main algorithmic layers:

  1. A Greedy Wrapper: This outer layer starts with an initial kernel and iteratively adds new kernels to a mixture. In each step, it looks for a new kernel parameter $\omega$ that improves the current model the most.
  2. The DC-Programming Engine: The core innovation is recognizing that the subproblem of finding the best new kernel parameter $\omega$ belongs to the class of DC functions. A DC function can be expressed as the difference between two convex functions ($f = g - h$). While non-convex, DC programs have specific properties that allow for global optimization using "cutting plane" methods.

Instead of checking every point on a grid, the DC algorithm uses linear approximations (cutting planes) to prune the search space. This effectively finds the global optimum for the kernel parameters without the "curse of dimensionality" that plagues standard branch-and-bound techniques.

Key Insights

  • Infinite Flexibility: By treating the kernel family as continuous, the model isn't locked into initial guesses. It can discover the exact variance or covariance structure the data requires.
  • The Power of DC Structure: Many machine learning problems are non-convex but possess a hidden "Difference of Convex" structure. Leveraging this structure provides a much more robust path to global optimality than simple local search or gradient descent.
  • Beyond Isotropic Gaussians: Most prior work used "isotropic" Gaussians (where the spread is uniform in all directions). This framework easily handles "anisotropic" kernels—for example, giving different importance to the left versus the right side of an image—which significantly improves performance on complex tasks.
  • Sparsity by Design: Because the algorithm is greedy, the final optimal kernel is usually a sparse mixture of only a few (typically fewer than 10) basic kernels, making the final model highly efficient for predictions.
Example distributions of kernel weights

Experimental Results

The researchers evaluated their algorithm using the MNIST dataset of handwritten digits, focusing on three specific binary classification tasks: Odd vs. Even digits, 3 vs. 8 (visually similar), and 4 vs. 7 (visually distinct). They compared their DC approach against standard SVMs, a "finite grid" method, and a previously proposed greedy method using local descent.

  • Superior Accuracy: On the "odd vs. even" task, the DC algorithm achieved a misclassification error of 6.5%, significantly outperforming the finite grid method (18.0%) and SVM-light (11.8%).
  • Computational Efficiency: When moving from one parameter to two (e.g., separate variances for different parts of an image), the DC algorithm proved much faster. It took about 5 minutes to solve, whereas the finite grid method took over an hour and still produced inferior results.
  • Robustness: The algorithm's performance remained stable even when the range of allowed variances was changed, proving it is not overly sensitive to the initial search window.

Limitations and Future Work

While highly effective, the approach has limitations. The authors noted that runtime increases significantly as more parameters are added (e.g., taking about an hour for 4 parameters), making scaling to high dimensions a challenge. To address this, they suggest combining the global DC search with faster local search heuristics. Finally, while the DC method is highly memory-efficient—avoiding the need to store massive pre-computed kernel matrices—it trades this memory savings for the computational cost of solving the cutting-plane subproblems.

Summary updated

BibTeX
@inproceedings{argyriou2006dc,
  author = {Andreas Argyriou and Raphael Hauser and Charles A. Micchelli and Massimiliano Pontil},
  title = {{A DC-programming algorithm for kernel selection}},
  booktitle = {International Conference on Machine Learning},
  year = {2006},
  doi = {10.1145/1143844.1143850},
}
Figure