Faster Support Vector Machines
This work addresses the scalability issue for SVM users dealing with millions of data points, offering a significant speedup while maintaining accuracy.
The paper tackles the time complexity of training support vector machines (SVMs) on large datasets by introducing a faster multilevel SVM that uses label propagation to build a problem hierarchy, achieving up to orders of magnitude speed improvements, such as being 15 times faster than ThunderSVM with comparable classification quality.
The time complexity of support vector machines (SVMs) prohibits training on huge data sets with millions of data points. Recently, multilevel approaches to train SVMs have been developed to allow for time-efficient training on huge data sets. While regular SVMs perform the entire training in one -- time consuming -- optimization step, multilevel SVMs first build a hierarchy of problems decreasing in size that resemble the original problem and then train an SVM model for each hierarchy level, benefiting from the solved models of previous levels. We present a faster multilevel support vector machine that uses a label propagation algorithm to construct the problem hierarchy. Extensive experiments indicate that our approach is up to orders of magnitude faster than the previous fastest algorithm while having comparable classification quality. For example, already one of our sequential solvers is on average a factor 15 faster than the parallel ThunderSVM algorithm, while having similar classification quality.