P-packSVM: Parallel Primal grAdient desCent Kernel SVM
- 1 December 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 677-686
- https://doi.org/10.1109/icdm.2009.29
Abstract
It is an extreme challenge to produce a nonlinear SVM classifier on very large scale data. In this paper we describe a novel P-packSVM algorithm that can solve the Support Vector Machine (SVM) optimization problem with an arbitrary kernel. This algorithm embraces the best known stochastic gradient descent method to optimize the primal objective, and has 1/ε dependency in complexity to obtain a solution of optimization error ε. The algorithm can be highly parallelized with a special packing strategy, and experiences sub-linear speed-up with hundreds of processors. We demonstrate that P-packSVM achieves accuracy sufficiently close to that of SVM-light, and overwhelms the state-of-the-art parallel SVM trainer PSVM in both accuracy and efficiency. As an illustration, our algorithm trains CCAT dataset with 800k samples in 13 minutes and 95% accuracy, while PSVM needs 5 hours but only has 92% accuracy. We at last demonstrate the capability of P-packSVM on 8 million training samples.Keywords
This publication has 13 references indexed in Scilit:
- Training linear SVMs in linear timePublished by Association for Computing Machinery (ACM) ,2006
- Parallel Sequential Minimal Optimization for the Training of Support Vector MachinesIEEE Transactions on Neural Networks, 2006
- Online Learning with KernelsIEEE Transactions on Signal Processing, 2004
- Solving large scale linear prediction problems using stochastic gradient descent algorithmsPublished by Association for Computing Machinery (ACM) ,2004
- A parallel solver for large quadratic programs in training support vector machinesParallel Computing, 2003
- Optimizing search engines using clickthrough dataPublished by Association for Computing Machinery (ACM) ,2002
- Learning to Classify Text Using Support Vector MachinesPublished by Springer Nature ,2002
- Primal-Dual Interior-Point MethodsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1997
- On the Implementation of a Primal-Dual Interior Point MethodSIAM Journal on Optimization, 1992
- Validity of the single processor approach to achieving large scale computing capabilitiesPublished by Association for Computing Machinery (ACM) ,1967