title: Analysis of programming properties and the row-column generation method for 1-norm support vector machines.
abstract: This paper deals with fast methods for training a 1-norm support vector machine (SVM). First, we define a specific class of linear programming with many sparse constraints, i.e., row-column sparse constraint linear programming (RCSC-LP). In nature, the 1-norm SVM is a sort of RCSC-LP. In order to construct subproblems for RCSC-LP and solve them, a family of row-column generation (RCG) methods is introduced. RCG methods belong to a category of decomposition techniques, and perform row and column generations in a parallel fashion. Specially, for the 1-norm SVM, the maximum size of subproblems of RCG is identical with the number of Support Vectors (SVs). We also introduce a semi-deleting rule for RCG methods and prove the convergence of RCG methods when using the semi-deleting rule. Experimental results on toy data and real-world datasets illustrate that it is efficient to use RCG to train the 1-norm SVM, especially in the case of small SVs.
authors.affiliation: Research Center of Machine Learning and Data Analysis, School of Computer Science and Technology, Soochow University, Suzhou 215006, Jiangsu, China. Electronic address: lizhang.ml@gmail.com.
authors.forename: Li
authors.initials: L
authors.lastname: Zhang
authors.forename: WeiDa
authors.initials: W
authors.lastname: Zhou
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016208:Databases, Factual; D006331:Heart Diseases / Q000453:epidemiology; D006798:Housing; D006801:Humans; D007198:Indians, North American; D016014:Linear Models; D008107:Liver Diseases / Q000453:epidemiology; D016011:Normal Distribution; D011382:Programming, Linear; D015203:Reproducibility of Results; D012984:Software; D060388:Support Vector Machine
keywords: 1-norm SVM; Column generation; Linear programming; Row–column generation; Sparse constraints