Accelerated Asynchronous Greedy Coordinate Descent Algorithm for SVMs

Accelerated Asynchronous Greedy Coordinate Descent Algorithm for SVMs

Bin Gu, Yingying Shan, Xiang Geng, Guansheng Zheng

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 2170-2176. https://doi.org/10.24963/ijcai.2018/300

Support vector machines play an important role in machine learning in the last two decades. Traditional SVM solvers (e.g. LIBSVM) are not scalable in the current big data era. Recently, a state of the art solver was proposed based on the asynchronous greedy coordinate descent (AsyGCD) algorithm. However, AsyGCD is still not scalable enough, and is limited to binary classification. To address these issues, in this paper we propose an asynchronous accelerated greedy coordinate descent algorithm (AsyAGCD) forĀ  SVMs. Compared with AsyGCD, our AsyAGCD has the following two-fold advantages: 1) our AsyAGCD is an accelerated version of AsyGCD because active set strategy is used. Specifically, our AsyAGCD can converge much fasterĀ  than AsyGCD for the second half of iterations. 2) Our AsyAGCD can handle more SVM formulations (including binary classification and regression SVMs) than AsyGCD. We provide the comparison of computational complexity of AsyGCD and our AsyAGCD. Experiment results on a variety of datasets and learning applications confirm that our AsyAGCD is much faster than the existing SVM solvers (including AsyGCD).
Keywords:
Machine Learning: Classification
Machine Learning: Machine Learning