A new decomposition method for support vector machines with polynomial convergence

Support vector machines (SVMs) are an important classifier which is widely used in pattern classification and machine learning. Recently large-scale classification problems in real world have attracted much attention where decomposition methods play an important role in solving SVMs. Although several decomposition algorithms have been applied in practice and proven to be convergent, the convergence speed is not easy to obtain which is important to analysis of different algorithms. The newly proposed algorithms based on rate certifying pair/set give us light to get the convergence speed in theory, but they suffer from high computational cost either due to more iterations to reach a tolerance of solution or to complexity in working set selection. A new simple decomposition algorithm based on a new philosophy is proposed in this paper. It has been proven that the working set selected by the new algorithm is a rate certifying set. Furthermore, compared with existing algorithms based on rate certifying pair/set, our algorithm provides a very good feature in combination of lower computational complexity in working set selection and faster convergence.