On Coresets for Support Vector Machines
This work addresses the computational bottleneck of SVM training for big data applications, offering a method to extend existing solvers to streaming and distributed settings, though it is incremental as it builds on known coreset concepts.
The paper tackles the problem of training Support Vector Machines (SVM) efficiently in large-scale and streaming data by developing a coreset construction algorithm that reduces data size while maintaining model competitiveness, with experimental results confirming its practical effectiveness in accelerating training.
We present an efficient coreset construction algorithm for large-scale Support Vector Machine (SVM) training in Big Data and streaming applications. A coreset is a small, representative subset of the original data points such that a models trained on the coreset are provably competitive with those trained on the original data set. Since the size of the coreset is generally much smaller than the original set, our preprocess-then-train scheme has potential to lead to significant speedups when training SVM models. We prove lower and upper bounds on the size of the coreset required to obtain small data summaries for the SVM problem. As a corollary, we show that our algorithm can be used to extend the applicability of any off-the-shelf SVM solver to streaming, distributed, and dynamic data settings. We evaluate the performance of our algorithm on real-world and synthetic data sets. Our experimental results reaffirm the favorable theoretical properties of our algorithm and demonstrate its practical effectiveness in accelerating SVM training.