Quadratic convergence of smoothing Newton's method for 0/1 loss optimization
File(s)
Accepted version
Author(s)
Zhou, Shenglong
Pan, Lili
Xiu, Naihua
Qi, Houduo
Type
Journal Article
Abstract
It has been widely recognized that the 0/1-loss function is one of the most natural choices for modelling classification errors, and it has a wide range of applications including support vector machines and 1-bit compressed sensing. Due to the combinatorial nature of the 0/1 loss function, methods based on convex relaxations or smoothing approximations have dominated the existing research and are often able to provide approximate solutions of good quality. However, those methods are not optimizing the 0/1 loss function directly and hence no optimality has been established for the original problem. This paper aims to study the optimality conditions of the 0/1 function minimization and for the first time to develop Newton's method that directly optimizes the 0/1 function with a local quadratic convergence under reasonable conditions. Extensive numerical experiments demonstrate its superior performance as one would expect from Newton-type methods.
Date Issued
2021-12-13
Date Acceptance
2021-09-05
Citation
SIAM Journal on Optimization, 2021, 31 (4), pp.3184-3211
ISSN
1052-6234
Publisher
Society for Industrial and Applied Mathematics
Start Page
3184
End Page
3211
Journal / Book Title
SIAM Journal on Optimization
Volume
31
Issue
4
Copyright Statement
© by SIAM. Unauthorized reproduction of this article is prohibited.
Identifier
https://epubs.siam.org/doi/10.1137/21M1409445
Subjects
0102 Applied Mathematics
0103 Numerical and Computational Mathematics
Operations Research
Publication Status
Published
Date Publish Online
2021-12-13