A Simple Decomposition Method for Support Vector Machines

Chih-Wei Hsu, Chih-Jen LinMachine Learning 2002 · OpenReview

Abstract

The decomposition method is currently one of the major methods for solving support vector machines. An important issue of this method is the selection of working sets. In this paper through the design of decomposition methods for bound-constrained SVM formulations we demonstrate that the working set selection is not a trivial task. Then from the experimental analysis we propose a simple selection of the working set which leads to faster convergences for difficult cases. Numerical experiments on different types of problems are conducted to demonstrate the viability of the proposed method.

Introduction

Training Support Vector Machines (SVMs) on large-scale datasets presents a significant computational challenge. At the core of SVM training is a Quadratic Programming (QP) problem involving an $l \times l$ matrix, where $l$ is the number of training samples. For modern datasets with tens of thousands of points, this matrix is often too large to fit in memory, necessitating the use of decomposition methods. These methods iteratively solve smaller sub-problems by selecting a small "working set" of variables to optimize while keeping others fixed.

The Working Set Selection Problem

A critical factor in the efficiency of decomposition methods is the strategy used to select the working set. Standard approaches, such as those implemented in $SVM^{light}$, typically select variables that most significantly violate the Karush-Kuhn-Tucker (KKT) optimality conditions. However, Hsu and Lin (2002) demonstrate that these traditional strategies can struggle, particularly when the penalty parameter $C$ is large, leading to slow convergence and "zig-zagging" behavior.

The "Free Variable" Bottleneck

The authors identify the number of "free variables"—those not at the boundaries 0 or $C$—as a primary bottleneck for convergence. When too many variables remain free, the algorithm struggles to find the global optimum efficiently because it only observes a small slice of the problem at a time.

Figure 3: Number of free variables vs. iterations. The proposed strategy (dashed line) converges significantly faster than the standard approach (solid line) by aggressively pushing variables toward their bounds.

To address this, the paper proposes a novel selection strategy that doesn't just focus on KKT violators but also selects variables that are "most satisfied" among the free variables. This approach forces variables to hit their bounds more quickly, effectively "shrinking" the complexity of the remaining optimization problem.

Experimental Results and Implementation

The proposed method was implemented in a tool called BSVM and benchmarked against 16 datasets from the Statlog and UCI repositories. The authors also introduced a simplified SVM formulation by adding a $\frac{1}{2}b^2$ term to the primal objective, which removes the linear equality constraint and simplifies the dual problem into a purely bound-constrained one.

Figure 4: Detailed iteration logs for the Heart dataset. This comparison shows how different selection strategies impact the objective function and the distribution of free vs. bounded (#C) variables.

Key findings include:

  • Significant Speedups: On the "Heart" dataset, a naive selection strategy required 590 iterations, whereas the proposed strategy reached the same optimum in only 50 iterations.
  • Efficiency at Scale: BSVM proved particularly effective in "difficult" scenarios with high $C$ values. For instance, on the "Adult4" dataset with an RBF kernel ($C=1000$), BSVM converged in 276 seconds, compared to over 1,700 seconds for $SVM^{light}$ without its shrinking heuristic.
  • Model Accuracy: The simplified formulation with the $b^2/2$ term maintained nearly identical generalization accuracy to standard SVMs across all test sets.

Conclusion and Future Work

Hsu and Lin's work highlights that working set selection is a non-trivial task that deeply impacts SVM training efficiency. By prioritizing the reduction of free variables, their method offers a robust alternative for large-scale optimization. Future work involves integrating "shrinking" heuristics—temporarily removing variables likely to remain at bounds—to further enhance performance, and adapting the strategy for problems with more complex linear constraints.

Summary updated

Abstract

The decomposition method is currently one of the major methods for solving support vector machines. An important issue of this method is the selection of working sets. In this paper through the design of decomposition methods for bound-constrained SVM formulations we demonstrate that the working set selection is not a trivial task. Then from the experimental analysis we propose a simple selection of the working set which leads to faster convergences for difficult cases. Numerical experiments on different types of problems are conducted to demonstrate the viability of the proposed method.
BibTeX
@article{hsu2002simple,
  author = {Chih-Wei Hsu and Chih-Jen Lin},
  title = {{A Simple Decomposition Method for Support Vector Machines}},
  journal = {Machine Learning},
  year = {2002},
  url = {https://openreview.net/forum?id=1aJFNa2ZR6},
}
Figure