A clipping dual coordinate descent algorithm for solving support vector machines

摘要

The dual coordinate descent (DCD) algorithm solves the dual problem of support vector machine (SVM) by minimizing a series of single-variable sub-problems with a random order at inner iterations. Apparently, this DCD algorithm gives a sightless update for all variables at each iteration, which leads to a slow speed. In this paper, we present a clipping dual coordinate descent (clipDCD) algorithm for solving the dual problem of SVM. In each iteration, this clipDCD algorithm only solves one single-variable sub-problem according to the maximal possibility-decrease strategy on objective value. We can easily implement this clipDCD algorithm since it has a much simpler formulation compared with the DCD algorithm. Our experiment results indicate that, if the clipDCD algorithm is employed, SVM, twin SVM (TWSVM) and its extensions not only obtain the same classification accuracies, but also take much faster learning speeds than those classifiers employing the DCD algorithm.