An efficient augmented Lagrangian method for support vector machine. (3rd July 2020)

• Record Type: Journal Article
• Authors: Yan, Yinqiao; Li, Qingna
• Is Part Of: Optimization methods and software. Volume 35:Number 4(2020)
• Page Start: 855
• Page End: 883
• Publication Date: 2020-07-03
• Subjects: Support vector machine -- augmented Lagrangian method -- semismooth Newton's method -- generalized Jacobian; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1734002
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: Support vector machine (SVM) has proved to be a successful approach for machine learning. Two typical SVM models are the L1-loss model for support vector classification (SVC) and ε -L1-loss model for support vector regression (SVR). Due to the non-smoothness of the L1-loss function in the two models, most of the traditional approaches focus on solving the dual problem. In this paper, we propose an augmented Lagrangian method for the L1-loss model, which is designed to solve the primal problem. By tackling the non-smooth term in the model with Moreau–Yosida regularization and the proximal operator, the subproblem in augmented Lagrangian method reduces to a non-smooth linear system, which can be solved via the quadratically convergent semismooth Newton's method. Moreover, the high computational cost in semismooth Newton's method can be significantly reduced by exploring the sparse structure in the generalized Jacobian. Numerical results on various datasets in LIBLINEAR show that the proposed method is competitive with the most popular solvers in both speed and accuracy.