A faster cutting plane algorithm with accelerated line search for linear SVM
作者：
Highlights：
• Faster cutting plane algorithms with accelerated line search are proposed to solve linear SVM.
• It proposes a novel linear-time line search solver while the existing strategy spends O(m log m) time.
• An optimized explicit piecewise linear function finding algorithm for multiclass linear SVM is derived.
• It can be proved to reduce the total SVM training time.
• Experiments demonstrate the effectiveness of the proposed algorithm.
摘要
•Faster cutting plane algorithms with accelerated line search are proposed to solve linear SVM.•It proposes a novel linear-time line search solver while the existing strategy spends O(m log m) time.•An optimized explicit piecewise linear function finding algorithm for multiclass linear SVM is derived.•It can be proved to reduce the total SVM training time.•Experiments demonstrate the effectiveness of the proposed algorithm.
论文关键词：Linear support vector machine,Binary classification,Root finding,Cutting plane algorithm
论文评审过程：Received 6 July 2016, Revised 13 December 2016, Accepted 2 February 2017, Available online 7 February 2017, Version of Record 25 March 2017.
论文官网地址：https://doi.org/10.1016/j.patcog.2017.02.006
