Source-linked AI summary
A Divide-and-Conquer Solver for Kernel Support Vector Machines
Cho-Jui Hsieh, Si Si, Inderjit S. Dhillon
TL;DR
Kernel SVMs are difficult to train at million-sample scale because their computation and memory demands are high. The paper proposes DC-SVM, which clusters data into independently solved subproblems, combines their solutions to initialize global optimization, and extends this design with multilevel clustering and early prediction. On covtype, it reports faster exact training, high accuracy, and substantially faster early prediction than existing solvers.
Problem
Kernel SVM computation becomes a bottleneck on datasets with millions of samples, while approximate solvers can reduce cost at the expense of prediction accuracy.
Method
DC-SVM clusters the data into independently solved subproblems, concatenates their solutions to initialize global coordinate descent, and extends this approach with multilevel clustering and early prediction.
Results
DC-SVM outperforms state-of-the-art exact and approximate kernel-SVM solvers in training speed, testing accuracy, and memory usage on large-scale datasets.
Takeaways & Limitations
Subproblem solutions can provide useful global support-vector estimates, enabling accurate kernel-SVM training and early high-accuracy prediction on large datasets.
Takeaways & Limitations
With very large datasets, sampling only 1000 points for two-step kernel kmeans may produce poor clustering and influence DC-SVM performance.
Abstract
from arXiv · showhide
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.
1 Introduction
Kernel SVMs become difficult to scale beyond one million samples because kernel-matrix computation and storage are expensive. DC-SVM addresses this bottleneck by solving clustered subproblems independently, combining their solutions, and using them to accelerate global optimization.
- Kernel SVM training becomes hard to scale beyond one million instances because computing and storing the kernel matrix is costly.
- DC-SVM partitions the full problem into independently solvable subproblems, then initializes a global coordinate descent solver with their combined solutions.
- The method uses kernel kmeans-based partitioning and theoretically links subproblem solutions and support vectors to the global solution.
- On covtype with half a million samples, DC-SVM reaches a 10^-6-accurate solution in 3 hours versus more than 22 hours for LIBSVM, while early prediction reaches 96.03% accuracy in 12 minutes.
2 Related Work
Prior kernel-SVM research reduces training cost through decomposition, model combination, landmark-based representations, and approximation. DC-SVM differs by preserving within-cluster relationships while using clustering to structure multilevel exact solving.
- Decomposition methods update subsets of variables to reduce SVM training memory, supporting libraries such as LIBSVM and SVMLight.
- Earlier divide-and-conquer approaches partition data or combine models, but may train subproblems nonindependently or target approximate solutions.
- Landmark and hierarchical methods represent data with cluster centers, whereas DC-SVM emphasizes preserving within-cluster relationships at lower levels.
- Kernel approximation, greedy basis selection, and online solvers reduce training or testing costs, while DC-SVM focuses on reducing kernel-SVM training time.
3 Divide and Conquer Kernel SVM with a single level
Single-level DC-SVM partitions the dual problem into clustered subproblems, concatenates their solutions, and uses the result to initialize global coordinate descent. Kernel clustering controls approximation error and support-vector identification, while partitioning reduces subproblem cost but creates a speed–accuracy trade-off.
- Problem formulation: The kernel SVM dual problem uses dual variables α, kernel matrix Q, and box constraints 0 ≤ α ≤ C.
- Divide step: DC-SVM divides the dual variables into k subsets and solves each corresponding subproblem independently.
- Computational savings: Dividing into k equal subproblems reduces solving time from O(n^3) to O(n^3/k^2) and space from O(n^2) to O(n^2/k^2).
- Conquer step: Concatenating the subproblem optima forms an approximate global solution that initializes the final coordinate descent solver.
- Approximate kernel: The concatenated solution is optimal for an approximate kernel that preserves within-cluster kernel values and removes between-cluster values.
- Approximation bound: The distance between approximate and global solutions is bounded by between-cluster kernel values, motivating balanced kernel kmeans partitions with small cross-cluster interactions.
- Empirical validation: On 10,000 covtype instances, the empirical objective gap tracks the theoretical bound across cluster counts and yields good global approximations.
- Support-vector identification: Support vectors from subproblems are expected to closely match global support vectors, enabling faster identification and convergence than LIBSVM shrinking.
4 Divide and Conquer SVM with multiple levels
Multilevel DC-SVM balances subproblem speed against initialization quality by progressively refining partitions and support-vector estimates. It also enables early prediction from lower-level models and reduces testing cost by restricting kernel evaluations to the relevant cluster.
- Motivation: The number of clusters trades faster subproblem solving against less accurate initialization for the global conquer step.Multilevel DC-SVM addresses this trade-off while retaining solutions close to the global optimum.
- Multilevel solver: At each level, DC-SVM partitions the data into clusters, solves the resulting subproblems independently, and uses lower-level solutions to initialize higher-level solvers.The implementation uses progressively organized levels and can initialize each level from the solution below it.
- Adaptive clustering: Two-step kernel kmeans can be limited on very large datasets because its O(nmd) cost restricts the number of sampled points.The implementation uses m = 1000, so sparse sampling can affect DC-SVM performance as dataset size grows.
- Early prediction: Lower-level models can support near-optimal early prediction, using the same approximated kernel during testing and assigning each instance to its nearest cluster.The procedure finds the nearest cluster and evaluates the model trained within that cluster.
- Early prediction: The proposed testing scheme reduces kernel-evaluation complexity from O(|S|d) to O(|S|d/k) by evaluating only support vectors in the instance’s cluster.It is reported to improve both test accuracy and testing time compared with alternative prediction methods.
- Adaptive clustering: Lower-level support vectors are used to refine clustering because they are likely to overlap with the support vectors of the whole model.This enables clustering to focus on a smaller, more relevant subset rather than the full dataset.
5 Experimental Results
Experiments evaluate DC-SVM across benchmark datasets, RBF and polynomial kernels, and competing exact, approximate, and online solvers. Results show faster convergence and strong testing accuracy, with especially large gains for the polynomial kernel.
- Experimental setup: Seven benchmark datasets are evaluated using dataset-specific splits, preprocessing, and binary-classification transformations.The experiments use raw or [0, 1]-scaled features depending on the dataset and specified training/testing splits.
- Experimental setup: The comparison includes exact solvers, approximate solvers, an online solver, and DC-SVM variants.The evaluated methods include LIBSVM, CascadeSVM, SpSVM, LLSVM, FastFood, LTPU, LaSVM, DC-SVM, and DC-SVM (early).
- RBF-kernel results: DC-SVM achieves faster objective-function convergence than state-of-the-art exact SVM solvers and higher testing accuracy in less training time than approximate solvers.The comparison uses relative objective error for exact solvers and testing-accuracy versus training-time comparisons across methods.
- RBF-kernel results: More than 50-fold speedup is observed while achieving higher testing accuracy.This comparison concerns reaching different testing-accuracy levels in the RBF-kernel experiments.
- Parameter sensitivity: Across 100 C, γ settings, DC-SVM is faster than LIBSVM on 96 settings, including a 1–2 times speed advantage when γ is small.The early variant is described as extremely fast and achieves almost the same or better accuracy when γ is small.
- Polynomial-kernel results: More than 100 times faster than LIBSVM and LaSVM is reported for the degree-3 polynomial-kernel experiments.The text attributes the large improvement partly to difficulty identifying the right support vectors for the competing methods.
- Runtime breakdown: Clustering time is almost constant at each level, while the remaining training time increases across levels.The reported breakdown separates clustering from SVM training time in the multilevel DC-SVM procedure.
6 Conclusions
DC-SVM divides kernel SVMs into independently solvable subproblems and uses their solutions to efficiently solve the original problem. The approach also incorporates early prediction and is reported to outperform exact and approximate solvers on large-scale datasets.
- DC-SVM divides the kernel SVM problem into smaller subproblems that can be solved independently and efficiently.
- The subproblem solutions are close to the original solution, motivating their use to efficiently solve the full kernel SVM problem.
- DC-SVM incorporates an early prediction strategy and significantly outperforms state-of-the-art exact and approximate nonlinear-kernel SVM solvers on large-scale datasets.