Support Vector Machine Classifier via Soft-Margin Loss

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: L₀/₁ soft-margin loss SVM (dubbed as L₀/₁ -SVM). Many of the existing (non) convex soft-margin losses can be viewed as one of the surrogates of the L₀/₁ soft-margin loss. Despite its discrete nature, we manage to establish the optimality theory for the L₀/₁ -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 L₀/₁ 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 L₀/₁ -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.