Support Vector Machine Classifier via Soft-Margin Loss
Huajun Wang, Yuan‐Hai Shao, Shenglong Zhou, Ce Zhang, Naihua Xiu
Abstract
Support vector machines (SVM) have drawn wide attention for the last two decades due to its extensive applications, so a vast body of work has developed optimization algorithms to solve SVM with various soft-margin losses. To distinguish all, in this paper, we aim at solving an ideal soft-margin loss SVM: <inline-formula><tex-math notation="LaTeX">$L_{0/1}$</tex-math></inline-formula> soft-margin loss SVM (dubbed as <inline-formula><tex-math notation="LaTeX">$L_{0/1}$</tex-math></inline-formula> -SVM). Many of the existing (non)convex soft-margin losses can be viewed as one of the surrogates of the <inline-formula><tex-math notation="LaTeX">$L_{0/1}$</tex-math></inline-formula> soft-margin loss. Despite its discrete nature, we manage to establish the optimality theory for the <inline-formula><tex-math notation="LaTeX">$L_{0/1}$</tex-math></inline-formula> -SVM including the existence of the optimal solutions, the relationship between them and P-stationary points. These not only enable us to deliver a rigorous definition of <inline-formula><tex-math notation="LaTeX">$L_{0/1}$</tex-math></inline-formula> support vectors but also allow us to define a working set. Integrating such a working set, a fast alternating direction method of multipliers is then proposed with its limit point being a locally optimal solution to the <inline-formula><tex-math notation="LaTeX">$L_{0/1}$</tex-math></inline-formula> -SVM. Finally, numerical experiments demonstrate that our proposed method outperforms some leading classification solvers from SVM communities, in terms of faster computational speed and a fewer number of support vectors. The bigger the data size is, the more evident its advantage appears.