Lehrstuhl Mathematik & InformatikOn the Complexity of Working Set Selection
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 (2004) and further analyzed (2005) by List and Simon. It is known that it efficiently approaches feasible solutions of minimum cost for any convex quadratic optimization problem. Here, we investigate its computational complexity when it is used for SVM-optimization. It turns out that, for variable size of the working set, the general policy poses an NP-hard working set selection problem. But a slight variation of it (sharing the convergence properties with the original policy) can be solved in polynomial time. For working sets of fixed size 2, the situation is even better. In this case, the general policy coincides with the ``rate certifying pair approach'' (introduced by Hush and Scovel). We show that maximum rate certifying pairs can be found in linear time, which leads to a quite efficient decomposition method with a polynomial convergence rate for SVM-optimization.