Support vector machine classifier via L0/1 soft-margin loss
File(s)
Author(s)
Wang, Huajun
Shao, Yuanhai
Zhou, Shenglong
Zhang, Ce
Xiu, Naihua
Type
Journal Article
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: L0/1 soft-margin loss SVM (dubbed as L0/1 -SVM). Many of the existing (non)convex soft-margin losses can be viewed as one of the surrogates of the L0/1 soft-margin loss. Despite its discrete nature, we manage to establish the optimality theory for the L0/1 -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 L0/1 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 L0/1 -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.
Date Issued
2022-10-01
Date Acceptance
2021-06-21
Citation
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44 (10), pp.7253-7265
ISSN
0162-8828
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Start Page
7253
End Page
7265
Journal / Book Title
IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume
44
Issue
10
Copyright Statement
© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
https://ieeexplore.ieee.org/document/9464733
Subjects
math.OC
math.OC
cs.LG
stat.ML
Artificial Intelligence & Image Processing
0801 Artificial Intelligence and Image Processing
0806 Information Systems
0906 Electrical and Electronic Engineering
Publication Status
Published
Date Publish Online
2021-06-24