A Divide-and-Conquer Solver for Kernel Support Vector Machines

Abstract

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.

Cited by in corpus (20)

• Compact Nonlinear Maps and Circulant Extensions
• A Survey of Machine Learning Methods and Challenges for Windows Malware Classification
• Distributed Inference for Linear Support Vector Machine
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• A Divide-and-Conquer Machine Learning Approach for Modelling Turbulent Flows
• Efficient Divide-And-Conquer Classification Based on Feature-Space Decomposition
• On the Complexity of Learning with Kernels
• Kernel Ridge Regression via Partitioning
• Parallelizing Spectral Algorithms for Kernel Learning
• Engineering fast multilevel support vector machines
• On Learning the Transformer Kernel
• Histogram Transform Ensembles for Large-scale Regression
• Hypothesis Testing of One-Sample Mean Vector in Distributed Frameworks
• Communication-Efficient Parallel Block Minimization for Kernel Machines
• Multi-Merge Budget Maintenance for Stochastic Gradient Descent SVM Training
• Speeding Up Budgeted Stochastic Gradient Descent SVM Training with Precomputed Golden Section Search
• Learning Data-adaptive Nonparametric Kernels
• Geometric Interpretation of Running Nyström-Based Kernel Machines and Error Analysis
• Two-stage Best-scored Random Forest for Large-scale Regression
• Generalization Properties of hyper-RKHS and its Applications