Multi-Order Information for Working Set Selection of Sequential Minimal Optimization

Qimao Yang, Changrong Li, Jun GuoAISTATS 2019

Introduction

Support Vector Machines (SVMs) remain a fundamental tool in machine learning for classification and regression tasks. However, training SVMs on large-scale datasets is computationally intensive. The Sequential Minimal Optimization (SMO) algorithm addresses this by decomposing the large quadratic programming problem into a series of sub-problems involving only two variables. The efficiency of SMO depends critically on the "working set selection" strategy—the method used to choose which two variables to update at each step.

While first-order methods use simple gradients and second-order methods (like those in the widely-used LIBSVM library) prioritize maximum immediate reduction of the objective function, these approaches can be suboptimal. Specifically, second-order methods may select pairs that yield a high local reduction but a very small update "stride," necessitating a large number of subsequent iterations to reach the global optimum. This paper proposes a "Multi-Order Information" (MOI) method to address this "greedy" limitation.

Methods: Multi-Order Information (MOI)

The proposed MOI approach shifts the focus from purely local optimization to a more balanced selection criterion. The authors define a new selection function $H$ that incorporates two key components:

  1. Descent Degree: The magnitude of the drop in the objective function value.
  2. Stride: The magnitude of the change in the variables (Lagrange multipliers).

By optimizing this multi-order function, the algorithm favors variable pairs that provide both a significant reduction in the objective value and a substantial movement toward the final solution. This prevents the solver from getting bogged down in tiny, incremental steps. Additionally, a relaxation factor ($λ$) is introduced to ensure that the selected variables strictly satisfy the Karush-Kuhn-Tucker (KKT) conditions, maintaining theoretical convergence guarantees.

Experimental Results

The MOI method was evaluated against the standard second-order selection in LIBSVM across a diverse set of benchmark datasets, ranging from small problems like heart and diabetes to large-scale datasets like skin_nonskin (approx. 245k instances).

Iteration Reduction

The primary finding was a consistent and significant reduction in the number of iterations required for convergence. In almost all cases, MOI outperformed the second-order method. For example, iterations for the heart dataset decreased by 17.93%, while the w1a dataset saw a staggering 27.36% reduction. On the large-scale skin_nonskin dataset, iterations were reduced by 23.01%.

Figure 4: Relative change in the number of iterations for small-scale datasets. Negative values (green bars) indicate a reduction in iterations compared to the standard LIBSVM approach.

Training Time and Cache Performance

While MOI consistently reduces iteration counts, the impact on total training time is more nuanced. The authors observed that MOI's selection pattern can lead to a lower cache hit rate for the kernel matrix compared to the more predictable greedy selection of LIBSVM. Consequently, the time savings are most pronounced in scenarios where the cache is small or insufficient, as the reduction in iterations outweighs the overhead of recomputing kernel elements.

Conclusion and Future Work

The Multi-Order Information approach provides a robust framework for improving SMO efficiency by considering the "stride" of updates alongside objective function descent. By sacrificing pure local greed for global progress, the method achieves significant reductions in iteration counts across varied datasets.

Future research directions include integrating MOI with parallel SMO algorithms and optimizing cache management strategies specifically for the MOI selection pattern to further bridge the gap between iteration reduction and total training time savings.

Summary updated

BibTeX
@inproceedings{yang2019multi,
  author = {Qimao Yang and Changrong Li and Jun Guo},
  title = {{Multi-Order Information for Working Set Selection of Sequential Minimal Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
}
Figure