BPPGD: Budgeted Parallel Primal Gradient Descent Kernel SVM on Spark
Jinchen Sai, Bai Wang, Bin Wu · 2016
Stochastic Gradient Descent (SGD) is the best known method to optimize the primal objective for linear support vector machines (SVM) to dispose large data. However, when equipped with kernel functions, SGD performance is vulnerable that causes unbounded linear growth in model size and update time with data size. This paper describes a budgeted parallel pack gradient descent algorithm (BPPGD) that can improve SVM optimize problem with Gaussian Radial Basis Function (RBF) to large-scale data and run efficiently on Apache Spark with high degree of parallelization. Apache Spark is a fast and general engine for large-scale data processing which has advantage on big data parallel computing and dealing with iterative algorithms. BPPGD algorithm has constant time complexity per update. It uses a new distributed hash table -- IndexedRDD to increase the parallel degree, packing strategy to improve SGD performance with reducing the number of communication and removal budget maintenance method to keep the number of support vectors (SVs). The experiment results show that BPPGD achieves higher accuracy than P-packSVM (Zhu et al., 2009) and BSGD (Zhuang et al., 2012) algorithms on Spark environment, and it takes shorter time.