Sparse conjugate directions pursuit with application to fixed-size kernel models

Peter Karsmakers, Kristiaan Pelckmans, Kris De Brabanter, Hugo Van hamme, Johan A. K. SuykensMachine Learning 2011 · DOI

Published in Machine Learning (2011), this research introduces Sparse Conjugate Directions Pursuit (SCDP), a novel optimization algorithm designed to bridge the gap between fast iterative solvers and the requirement for sparse models in machine learning. SCDP is a greedy algorithm that combines the computational efficiency of Conjugate Gradient (CG) with the sparsity-inducing properties of Matching Pursuit.

The Challenge: Efficiency vs. Sparsity

In machine learning, many problems are framed as solving linear systems of the form $Xw = y$. When dealing with more measurements than parameters—an over-determined system—we typically seek a "least squares" solution.

Figure 1: Representation of an over-determined linear system where the number of observations exceeds the number of parameters.

Standard solutions to these systems are usually "dense," meaning every parameter has a non-zero value. Dense models present significant drawbacks:

  1. Overfitting: They may capture noise rather than underlying patterns.
  2. Latency: They are slow to evaluate in real-time applications.
  3. Scalability: They struggle with "Big Data" volumes.

The authors specifically target Least Squares Support Vector Machines (LS-SVMs). Unlike standard SVMs, LS-SVMs are not naturally sparse, making them difficult to scale to large datasets without a specialized solver.

Methodology: Sparse Conjugate Directions Pursuit

SCDP adapts the classical Conjugate Gradient algorithm to enforce sparsity through an iterative process. It sits within a broader taxonomy of heuristic sparse solvers, offering a middle ground between $L_1$ regularization and simple greedy methods.

Figure 4: Taxonomy of heuristics for solving sparse linear systems, highlighting the greedy and L1-based approaches.

Key Algorithmic Features

  • Iterative Cardinality: The algorithm starts with a zero vector and adds exactly one new non-zero coefficient per iteration. At iteration $k$, the model size is exactly $k$.
  • Greedy Selection: In each step, the algorithm selects the component with the largest absolute residual—the feature that currently explains the most remaining error.
  • Conjugate Basis: Unlike standard Matching Pursuit, SCDP maintains a set of "conjugate" directions. This ensures each new step is optimal relative to all previous steps, leading to faster convergence and direct least-squares estimates without the "shrinkage bias" found in LASSO.
  • SCDPP (Probabilistic Speed-up): For massive datasets, a probabilistic version searches only a random subset of components in each step, drastically reducing the computational bottleneck.

Integration with Fixed-Size LS-SVMs

To make kernel methods viable for large datasets, the authors apply SCDP to "Fixed-Size" LS-SVMs. By using the Nyström approximation to map data into a lower-dimensional primal space, they transform complex kernel problems into the over-determined linear systems that SCDP is optimized to solve.

Key Results and Insights

The algorithm was evaluated on 13 UCI datasets and several large-scale benchmarks, including the adult (~30,000 points) and gamma telescope (~12,000 points) datasets.

  • Superior Speed: SCDP was 7 to 10 times faster than LARS, LASSO, or Matching Pursuit on large datasets. This efficiency stems from reaching high-quality solutions in fewer iterations without requiring post-processing de-biasing steps.
  • Extreme Sparsity: On the adult dataset, SCDP achieved comparable accuracy to a standard SVM using only 166 prototype vectors, whereas the standard SVM required over 10,000 support vectors.
  • Model Selection: Because the number of iterations corresponds directly to model size, cross-validation can be used as an early-stopping mechanism to automatically find the optimal balance between complexity and accuracy.

Limitations

While powerful, SCDP relies on the initial selection of "Prototype Vectors" (typically via k-center clustering), which means it does not guarantee a global optimum in the same way convex solvers do. Additionally, the algorithm requires storing previous conjugate directions, leading to a memory complexity of $O(D + 2k + k^2)$, which may be a consideration for extremely high-dimensional problems.

Summary updated

BibTeX
@article{karsmakers2011sparse,
  author = {Peter Karsmakers and Kristiaan Pelckmans and Kris De Brabanter and Hugo Van hamme and Johan A. K. Suykens},
  title = {{Sparse conjugate directions pursuit with application to fixed-size kernel models}},
  journal = {Machine Learning},
  year = {2011},
  doi = {10.1007/s10994-011-5253-8},
}
Figure