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\sqrt{2K_{n}}+8\sqrt{\lambda})^{-2} \lambda \epsilon_{p}^{2}$ 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 {\em decomposition} algorithms and describe new decomposition algorithms with guaranteed accuracy and run time. In particular, for {\em $\tau$--rate certifying} decomposition algorithms we establish the optimality of $\tau = 1/(n-1)$ and we extend the recent algorithm of \cite{Si04a} to form two new {\em composite} algorithms that also achieve the $\tau = 1/(n-1)$ iteration bound in \cite{LiSi05a} but yield faster run times in practice. We also exploit the $\tau$--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 {\em 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.
D. Hush, P. Kelly, C. Scovel and I. Steinwart, QP Algorithms with Guaranteed Accuracy and Run Time for Support Vector Machines. Journal of Machine Learning Research, Vol. 7, pp. 733-769, 2006. Los Alamos National Laboratory Technical Report LA-UR-05-5165. [ Abstract | Postscript (787 KB) | PDF (627 KB) ]
