Budgeted mini-batch parallel gradient descent for support vector machines on Spark

Mini-batch gradient descent (MBGD) is an attractive choice for support vector machines (SVM), because processing part of examples at a time is advantageous when disposing large data. Similar to other SVM learning algorithms, MBGD is vulnerable to the curse of kernelization when equipped with kernel functions, which results in unbounded linear growth in model size and update time with data size. This paper presents a budgeted mini-batch parallel gradient descent algorithm (BMBPGD) for large-scale kernel SVM training which can run efficiently on Apache Spark. Spark is a fast and general engine for large-scale data processing which is originally intended to deal with iterative algorithms. BMBPGD algorithm has constant space and time complexity per update. It uses removal budget maintenance method to keep the number of support vectors (SVs). The experiment results show that BMBPGD achieves higher accuracy than SVMWithSGD algorithm in MLlib on Spark environment, and it takes much shorter time than LibSVM.