Lehrstuhl Mathematik & InformatikOn the Complexity of Working Set Selection
Abstract. The decomposition method is currently one of the major methods for solving the convex quadratic optimization problems being associated with Support Vector Machines (SVM-optimization). A key issue in this approach is the policy for working set selection. We would like to find policies that realize (as good as possible) three goals simultaneously: ``(fast) convergence to an optimal solution'', ``efficient procedures for working set selection'', and ``high degree of generality'' (including typical variants of SVM-optimization as special cases). In this paper, we study a general policy for working set selection that has been proposed quite recently. It is known that it leads to convergence for any convex quadratic optimization problem. Here, we investigate its computational complexity when it is used for SVM-optimization. We show that it poses an NP-complete working set selection problem, but a slight variation of it (sharing the convergence properties with the original policy) can be solved in polynomial time. We show furthermore that so-called ``rate certifying pairs'' (introduced by Hush and Scovel) can be found in linear time, which leads to a quite efficient decomposition method with a polynomial convergence rate for SVM-optimization.