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

arXiv: https://arxiv.org/abs/1311.0914 · HTML: https://mlsanity.com/paper/1311.0914/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2013.

## Built on by (most cited first, 8 of 8)

- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [Decentralized Bayesian Learning with Metropolis-Adjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2107.07211/) (2021)
- [Nys-Newton: Nystr"om-Approximated Curvature for Stochastic Optimization](https://mlsanity.com/paper/2110.08577/) (2021)
- [Scalable Optimal Margin Distribution Machine](https://mlsanity.com/paper/2305.04837/) (2023)
- [An Accurate and Efficient Large-scale Regression Method through Best Friend Clustering](https://mlsanity.com/paper/2104.10819/) (2021)
- [Learning using granularity statistical invariants for classification](https://mlsanity.com/paper/2403.20122/) (2024)
- [Robust and Explainable Divide-and-Conquer Learning for Intrusion Detection](https://mlsanity.com/paper/2605.02015/) (2026)

## Abstract (arXiv)

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.