We describe a support vector machine (SVM) classifier design algorithm called L1--SVMD that produces approximate solutions with guaranteed accuracy and runs in polynomial time. This algorithm computes an approximate solution to the L1-SVM quadratic programming (QP) problem using a two stage approach where the first stage uses Simon's decomposition algorithm \cite{HuKeScSt05a,Si04a,LiSi05a} to compute an approximate solution to a dual QP, and the second stage constructs an approximate primal solution from the approximate dual solution. For the second stage we establish a general method for constructing primal solutions with accuracy $\epsilon_{p}$ from dual solutions with accuracy $\epsilon_{d}$ by solving a set of {\em converse dual equations}, and then we design an efficient algorithm that approximately solves these equations to yield approximate primal solutions with accuracy $\epsilon_{p} \propto \sqrt{\epsilon_{d}}$. For the L1--SVMD algorithm we develop a run time bound that depends on the regularization parameter $\lambda$, the accuracy $\epsilon_{p}$, the number of training samples $n$, and the kernel.
D. Hush, C. Scovel, and I. Steinwart, Polynomial Time Algorithms for Computing Approximate SVM Solutions with Guaranteed Accuracy. Los Alamos National Laboratory Technical Report LA-UR-05-7738, 2005. [ Abstract | Postscript (288 KB) | PDF (227 KB) ]
