Polynomial-time decomposition algorithms for support vector machines

This paper studies the convergence properties of a general class of decomposition algorithms for support vector machines (SVMs). We provide a model algorithm for decomposition, and prove necessary and sufficient conditions for stepwise improvement of this algorithm. We introduce a simple "rate certifying" condition and prove a polynomial-time bound on the rate of convergence of the model algorithm when it satisfies this condition. Although it is not clear that existing SVM algorithms satisfy this condition, we provide a version of the model algorithm that does. For this algorithm we show that when the slack multiplier C satisfies root1/2 less than or equal to Cless than or equal to mL, where m is the number of samples and L is a matrix norm, then it takes no more than 4LC(2)m(4)/epsilon iterations to drive the criterion to within epsilon of its optimum.