QP algorithms with guaranteed accuracy and run time for support vector machines

We describe polynomial-time algorithms that produce approximate solutions with guaranteed accuracy for a class of QP problems that are used in the design of support vector machine classifiers. These algorithms employ a two-stage process where the first stage produces an approximate solution to a dual QP problem and the second stage maps this approximate dual solution to an approximate primal solution. For the second stage we describe an O(n log n) algorithm that maps an approximate dual solution with accuracy (2 root 2K(n) + 8 root lambda)(-2) lambda epsilon(2)(p) to an approximate primal solution with accuracy epsilon(p) where n is the number of data samples, K-n is the maximum kernel value over the data and lambda > 0 is the SVM regularization parameter. For the first stage we present new results for decomposition algorithms and describe new decomposition algorithms with guaranteed accuracy and run time. In particular, for tau-rate certifying decomposition algorithms we establish the optimality of tau = 1/(n - 1). In addition we extend the recent tau = 1/(n - 1) algorithm of Simon ( 2004) to form two new composite algorithms that also achieve the t = 1/( n- 1) iteration bound of List and Simon ( 2005), but yield faster run times in practice. We also exploit the t - rate certifying property of these algorithms to produce new stopping rules that are computationally efficient and that guarantee a specified accuracy for the approximate dual solution. Furthermore, for the dual QP problem corresponding to the standard classification problem we describe operational conditions for which the Simon and composite algorithms possess an upper bound of O(n) on the number of iterations. For this same problem we also describe general conditions for which a matching lower bound exists for any decomposition algorithm that uses working sets of size 2. For the Simon and composite algorithms we also establish an O(n(2)) bound on the overall run time for the first stage. Combining the first and second stages gives an overall run time of O(n(2)(c(k) + 1)) where c(k) is an upper bound on the computation to perform a kernel evaluation. Pseudocode is presented for a complete algorithm that inputs an accuracy epsilon(p) and produces an approximate solution that satisfies this accuracy in low order polynomial time. Experiments are included to illustrate the new stopping rules and to compare the Simon and composite decomposition algorithms.