Faster SVM Training via Conjugate SMO

2020/03/19 by Torres-Barrán, Alberto, Alaíz, Carlos, Dorronsoro, José R.
#68Q32 #68W40 (Secondary) #90C25 (Primary) 65B10 #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2003.08719

Abstract

We propose an improved version of the SMO algorithm for training classification and regression SVMs, based on a Conjugate Descent procedure. This new approach only involves a modest increase on the computational cost of each iteration but, in turn, usually results in a substantial decrease in the number of iterations required to converge to a given precision. Besides, we prove convergence of the iterates of this new Conjugate SMO as well as a linear rate when the kernel matrix is positive definite. We have implemented Conjugate SMO within the LIBSVM library and show experimentally that it is faster for many hyper-parameter configurations, being often a better option than second order SMO when performing a grid-search for SVM tuning.

Related

• The Planning-ahead SMO Algorithm
• The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines
• Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations
• MaxMin-L2-SVC-NCH: A Novel Approach for Support Vector Classifier Training and Parameter Selection
• Training a Support Vector Machine in the Primal