A Divide-and-Conquer Solver for Kernel Support Vector Machines
This addresses the scalability issue for kernel SVM users dealing with millions of samples, offering a significant speedup with competitive accuracy, though it is an incremental improvement over existing methods.
The paper tackles the computational bottleneck of kernel SVMs on large datasets by proposing a divide-and-conquer solver (DC-SVM) that partitions the problem via clustering and efficiently solves subproblems, achieving up to 7 times faster training for exact solutions and over 100 times faster with early prediction while maintaining high accuracy (e.g., 96.15% on covtype).
The kernel support vector machine (SVM) is one of the most widely used classification methods; however, the amount of computation required becomes the bottleneck when facing millions of samples. In this paper, we propose and analyze a novel divide-and-conquer solver for kernel SVMs (DC-SVM). In the division step, we partition the kernel SVM problem into smaller subproblems by clustering the data, so that each subproblem can be solved independently and efficiently. We show theoretically that the support vectors identified by the subproblem solution are likely to be support vectors of the entire kernel SVM problem, provided that the problem is partitioned appropriately by kernel clustering. In the conquer step, the local solutions from the subproblems are used to initialize a global coordinate descent solver, which converges quickly as suggested by our analysis. By extending this idea, we develop a multilevel Divide-and-Conquer SVM algorithm with adaptive clustering and early prediction strategy, which outperforms state-of-the-art methods in terms of training speed, testing accuracy, and memory usage. As an example, on the covtype dataset with half-a-million samples, DC-SVM is 7 times faster than LIBSVM in obtaining the exact SVM solution (to within $10^{-6}$ relative error) which achieves 96.15% prediction accuracy. Moreover, with our proposed early prediction strategy, DC-SVM achieves about 96% accuracy in only 12 minutes, which is more than 100 times faster than LIBSVM.