2008 | Cho-Jui Hsieh, Kai-Wei Chang, Chih-Jen Lin, S. Sathiya Keerthi, S. Sundararajan
This paper presents a dual coordinate descent method for large-scale linear Support Vector Machines (SVM) with L1- and L2-loss functions. The method is simple and achieves an ε-accurate solution in O(log(1/ε)) iterations. It is significantly faster than state-of-the-art solvers such as Pegasos, TRON, SVM^perf, and a recent primal coordinate descent implementation. The algorithm solves the dual problem of SVM, which involves bound constraints on the dual variables. It uses a random order of sub-problems at each iteration, leading to fast training. The method also incorporates a shrinking technique to reduce the size of the optimization problem by eliminating variables that are at their bounds. The algorithm is efficient for large-scale linear SVM problems and has been shown to outperform other methods in experiments. The method is related to decomposition methods for nonlinear SVM and has been shown to be more efficient for linear SVM. The algorithm is implemented in C/C++ with double precision and has been tested on various datasets, including a9a, real-sim, news20, rcv1, and astro-physic. The results show that the dual coordinate descent method is significantly faster than other solvers for both L1- and L2-SVM.This paper presents a dual coordinate descent method for large-scale linear Support Vector Machines (SVM) with L1- and L2-loss functions. The method is simple and achieves an ε-accurate solution in O(log(1/ε)) iterations. It is significantly faster than state-of-the-art solvers such as Pegasos, TRON, SVM^perf, and a recent primal coordinate descent implementation. The algorithm solves the dual problem of SVM, which involves bound constraints on the dual variables. It uses a random order of sub-problems at each iteration, leading to fast training. The method also incorporates a shrinking technique to reduce the size of the optimization problem by eliminating variables that are at their bounds. The algorithm is efficient for large-scale linear SVM problems and has been shown to outperform other methods in experiments. The method is related to decomposition methods for nonlinear SVM and has been shown to be more efficient for linear SVM. The algorithm is implemented in C/C++ with double precision and has been tested on various datasets, including a9a, real-sim, news20, rcv1, and astro-physic. The results show that the dual coordinate descent method is significantly faster than other solvers for both L1- and L2-SVM.