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.
Standard solutions to these systems are usually "dense," meaning every parameter has a non-zero value. Dense models present significant drawbacks:
- Overfitting: They may capture noise rather than underlying patterns.
- Latency: They are slow to evaluate in real-time applications.
- 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.
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