An efficient parallel and distributed solution to nonconvex penalized linear SVMs

GUAN Lei; SUN Tao; QIAO Lin-bo; YANG Zhi-hui; LI Dong-sheng; GE Ke-shi; LU Xi-cheng

doi:10.1631/FITEE.1800566

Your Location：

Home >

Browse articles >

An efficient parallel and distributed solution to nonconvex penalized linear SVMs

Regular Papers | Updated：2022-05-19

- An efficient parallel and distributed solution to nonconvex penalized linear SVMs
- 一种有效求解非凸正则化线性支持向量机的并行与分布式方法
- Frontiers of Information Technology & Electronic Engineering Vol. 21, Issue 4, Pages: 587-603(2020)
- Affiliations：
  
  College of Computer, National University of Defense Technology, Changsha 410073, China
  School of Computer Science, Fudan University, Shanghai 201203, China
  Shanghai Key Laboratory of Data Science, Shanghai 201203, China
- Author bio：
  
  [ "Lei GUAN, E-mail: guanleics@gmail.com" ]
  [ "Tao SUN, E-mail: nudtsuntao@163.com" ]
  Dong-sheng LI, E-mail: dsli@nudt.edu.cn
- Funds：
- DOI：10.1631/FITEE.1800566
  CLC： TP391
- Received：14 September 2018，
  
  Revised：2019-;8-12，
  
  Published Online：05 September 2019，
  
  Published：2020-04
- Accepted：
Scan QR Code
GUAN Lei, SUN Tao, QIAO Lin-bo, et al. An efficient parallel and distributed solution to nonconvex penalized linear SVMs[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(4): 587-603.
DOI：

GUAN Lei, SUN Tao, QIAO Lin-bo, et al. An efficient parallel and distributed solution to nonconvex penalized linear SVMs[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(4): 587-603. DOI： 10.1631/FITEE.1800566.

摘要

支持向量机（SVM）被视为线性分类的有力工具。与可以产生稀疏效果的非凸惩罚项组合时，SVM能同时执行分类和变量选择。然而，由于其不可微、非凸和非平滑特性，非凸正则化SVM通常难以有效求得全局最优解。已有针对非凸正则化SVM的求解方案通常以串行方式求解，因而无法充分利用现代多核机器的并行处理能力。另一方面，现实世界中数据多以分布式方式存储，迫切需要一种并行与分布式方法求解非凸正则化SVM问题。为应对这一挑战，本文提出一种基于交替方向乘子法（ADMM）的并行算法高效求解非凸正则化SVM问题。采用有效技术降低并行算法的计算与同步开销。时间复杂度分析证明所提并行算法具有低复杂度。此外，该并行算法能保证收敛性。在LIBSVM数据集上的实验证明了所提并行算法的有效性。

Abstract

Support vector machines (SVMs) have been recognized as a powerful tool to perform linear classification. When combined with the sparsity-inducing nonconvex penalty

SVMs can perform classification and variable selection simultaneously. However

the nonconvex penalized SVMs in general cannot be solved globally and efficiently due to their nondifferentiability

nonconvexity

and nonsmoothness. Existing solutions to the nonconvex penalized SVMs typically solve this problem in a serial fashion

which are unable to fully use the parallel computing power of modern multi-core machines. On the other hand

the fact that many real-world data are stored in a distributed manner urgently calls for a parallel and distributed solution to the nonconvex penalized SVMs. To circumvent this challenge

we propose an efficient alternating direction method of multipliers (ADMM) based algorithm that solves the nonconvex penalized SVMs in a parallel and distributed way. We design many useful techniques to decrease the computation and synchronization cost of the proposed parallel algorithm. The time complexity analysis demonstrates the low time complexity of the proposed parallel algorithm. Moreover

the convergence of the parallel algorithm is guaranteed. Experimental evaluations on four LIBSVM benchmark datasets demonstrate the efficiency of the proposed parallel algorithm.

关键词

Keywords

references

Z Allen-Zhu , , , E Hazan . . Variance reduction for faster non-convex optimization . . Proc 33$^\text{rd}$ Int Conf on Machine Learning , , 2016 . . p.699 - - 707 . . . .

S Boyd , , , N Parikh , , , E Chu , , , 等 . . Distributed optimization and statistical learning via the alternating direction method of multipliers . . Found Trends Mach Learn , , 2011 . . 3 ( ( 1 ): ): 1 - - 122 . . DOI: 10.1561/2200000016 http://doi.org/10.1561/2200000016 . .

EJ Candès , , , MB Wakin , , , SP Boyd . . Enhancing sparsity by reweighted $\ell_1$ minimization . . J Fourier Anal Appl , , 2008 . . 14 ( ( 5-6 ): ): 877 - - 905 . . DOI: 10.1007/s00041-008-9045-x http://doi.org/10.1007/s00041-008-9045-x . .

A Daneshmand , , , F Facchinei , , , V Kungurtsev , , , 等 . . Hybrid random/deterministic parallel algorithms for convex and nonconvex big data optimization . . IEEE Trans Signal Process , , 2015 . . 63 ( ( 15 ): ): 3914 - - 3929 . . DOI: 10.1109/TSP.2015.2436357 http://doi.org/10.1109/TSP.2015.2436357 . .

Lorenzo P di , , , G Scutari . . Distributed nonconvex optimization over networks . . IEEE 6$^\text{th}$ Int Workshop on Computational Advances in Multi-sensor Adaptive Processing , , 2015 . . p.229 - - 232 . . DOI: 10.1109/CAMSAP.2015.7383778 http://doi.org/10.1109/CAMSAP.2015.7383778 . .

F Facchinei , , , G Scutari , , , S Sagratella . . Parallel selective algorithms for nonconvex big data optimization . . IEEE Trans Signal Process , , 2015 . . 63 ( ( 7 ): ): 1874 - - 1889 . . DOI: 10.1109/TSP.2015.2399858 http://doi.org/10.1109/TSP.2015.2399858 . .

JQ Fan , , , RZ Li . . Variable selection via nonconcave penalized likelihood and its oracle properties . . J Am Stat Assoc , , 2001 . . 96 ( ( 456 ): ): 1348 - - 1360 . . DOI: 10.1198/016214501753382273 http://doi.org/10.1198/016214501753382273 . .

PH Gong , , , CS Zhang , , , ZS Lu , , , 等 . . A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems . . Proc Int Conf on Machine Learning , , 2013 . . p.37 - - 45 . . . .

L Guan , , , LB Qiao , , , DS Li , , , 等 . . An efficient ADMM-based algorithm to nonconvex penalized support vector machines . . Proc 18$.{\textrm{th}}$ IEEE Int Conf on Data Mining , , 2018 . . p.1209 - - 1216 . . DOI: 10.1109/ICDMW.2018.00173 http://doi.org/10.1109/ICDMW.2018.00173 . .

MY Hong , , , ZQ Luo , , , M Razaviyayn . . Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems . . SIAM J Optim , , 2016 . . 26 ( ( 1 ): ): 337 - - 364 . . DOI: 10.1137/140990309 http://doi.org/10.1137/140990309 . .

L Laporte , , , R Flamary , , , S Canu , , , 等 . . Nonconvex regularizations for feature selection in ranking with sparse SVM . . IEEE Trans Neur Netw Learn Syst , , 2014 . . 25 ( ( 6 ): ): 1118 - - 1130 . . DOI: 10.1109/TNNLS.2013.2286696 http://doi.org/10.1109/TNNLS.2013.2286696 . .

HC Liu , , , T Yao , , , RZ Li . . Global solutions to folded concave penalized nonconvex learning . . Ann Stat , , 2016 . . 44 ( ( 2 ): ): 629 - - 659 . . DOI: 10.1214/15-AOS1380 http://doi.org/10.1214/15-AOS1380 . .

R Mazumder , , , JH Friedman , , , T Hastie . . SparseNet: coordinate descent with nonconvex penalties . . J Am Stat Assoc , , 2011 . . 106 ( ( 495 ): ): 1125 - - 1138 . . DOI: 10.1198/jasa.2011.tm09738 http://doi.org/10.1198/jasa.2011.tm09738 . .

P Ochs , , , YJ Chen , , , T Brox , , , 等 . . iPiano: inertial proximal algorithm for nonconvex optimization . . SIAM J Imag Sci , , 2014 . . 7 ( ( 2 ): ): 1388 - - 1419 . . DOI: 10.1137/130942954 http://doi.org/10.1137/130942954 . .

M Razaviyayn , , , MY Hong , , , ZQ Luo , , , 等 . . Parallel successive convex approximation for nonsmooth nonconvex optimization . . Proc 27$^\text{th}$ Int Conf on Neural Information Processing Systems , , 2014 . . p.1440 - - 1448 . . . .

SJ Reddi , , , S Sra , , , B Poczos , , , 等 . . Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization . . Proc 30$^\text{th}$ Conf on Neural Information Processing Systems , , 2016 . . p.1145 - - 1153 . . . .

G Scutari , , , F Facchinei , , , L Lampariello . . Parallel and distributed methods for constrained nonconvex optimization—Part Ⅰ: theory . . IEEE Trans Signal Process , , 2017 . . 65 ( ( 8 ): ): 1929 - - 1944 . . DOI: 10.1109/TSP.2016.2637317 http://doi.org/10.1109/TSP.2016.2637317 . .

J Sherman , , , WJ Morrison . . Adjustment of an inverse matrix corresponding to a change in one element of a given matrix . . Ann Math Stat , , 1950 . . 21 ( ( 1 ): ): 124 - - 127 . . DOI: 10.1214/aoms/1177729893 http://doi.org/10.1214/aoms/1177729893 . .

T Sun , , , H Jiang , , , LZ Cheng , , , 等 . . A convergence frame for inexact nonconvex and nonsmooth algorithms and its applications to several iterations . . 2017a . . https://arxiv.org/abs/1709.04072 https://arxiv.org/abs/1709.04072 , , . .

T Sun , , , H Jiang , , , LZ Cheng . . Iteratively linearized reweighted alternating direction method of multipliers for a class of nonconvex problems . . 2017b . . https://arxiv.org/abs/1709.00483 https://arxiv.org/abs/1709.00483 , , . .

T Sun , , , PH Yin , , , LZ Cheng , , , 等 . . Alternating direction method of multipliers with difference of convex functions . . Adv Comput Math , , 2018a . . 44 ( ( 3 ): ): 723 - - 744 . . DOI: 10.1007/s10444-017-9559-3 http://doi.org/10.1007/s10444-017-9559-3 . .

T Sun , , , PH Yin , , , DS Li , , , 等 . . Non-ergodic convergence analysis of heavy-ball algorithms . . 2018b . . https://arxiv.org/abs/1811.01777v2 https://arxiv.org/abs/1811.01777v2 , , . .

Y Sun , , , G Scutari , , , D Palomar . . Distributed nonconvex multiagent optimization over time-varying networks . . Proc 50$^\text{th}$ Asilomar Conf on Signals, Systems and Computers , , 2016 . . p.788 - - 794 . . DOI: 10.1109/ACSSC.2016.7869154 http://doi.org/10.1109/ACSSC.2016.7869154 . .

Y Wang , , , WT Yin , , , JS Zeng . . Global convergence of ADMM in nonconvex nonsmooth optimization . . 2015 . . https://arxiv.org/abs/1511.06324 https://arxiv.org/abs/1511.06324 , , . .

CH Zhang . . Nearly unbiased variable selection under minimax concave penalty . . Ann Stat , , 2010 . . 38 ( ( 2 ): ): 894 - - 942 . . DOI: 10.1214/09-AOS729 http://doi.org/10.1214/09-AOS729 . .

HH Zhang , , , J Ahn , , , XD Lin , , , 等 . . Gene selection using support vector machines with non-convex penalty . . Bioinformatics , , 2006 . . 22 ( ( 1 ): ): 88 - - 95 . . DOI: 10.1093/bioinformatics/bti736 http://doi.org/10.1093/bioinformatics/bti736 . .

SB Zhang , , , H Qian , , , XJ Gong . . An alternating proximal splitting method with global convergence for nonconvex structured sparsity optimization . . Proc 30$^\text{th}$ AAAI Conf on Artificial Intelligence , , 2016 . . p.2330 - - 2336 . . . .

T Zhang . . Analysis of multi-stage convex relaxation for sparse regularization . . J Mach Learn Res , , 2010 . . 11 1081 - - 1107 . . . .

X Zhang , , , YC Wu , , , L Wang , , , 等 . . Variable selection for support vector machines in moderately high dimensions . . J R Stat Soc Ser B , , 2016 . . 78 ( ( 1 ): ): 53 - - 76 . . DOI: 10.1111/rssb.12100 http://doi.org/10.1111/rssb.12100 . .

YM Zhang , , , DS Li , , , CX Guo , , , 等 . . CubicRing: exploiting network proximity for distributed in-memory key-value store . . IEEE/ACM Trans Netw , , 2017 . . 25 ( ( 4 ): ): 2040 - - 2053 . . DOI: 10.1109/TNET.2017.2669215 http://doi.org/10.1109/TNET.2017.2669215 . .

Views

197

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A non-group parallel frequent pattern mining algorithm based on conditional patterns

A robust intelligent audio watermarking scheme using support vector machine

Performance analysis of new word weighting procedures for opinion mining

Using Kinect for real-time emotion recognition via facial expressions

Related Author

Hang ZHOU

Dong-dai ZHOU

Jin-peng ZHOU

Kun YANG

Zhe-jun KUANG

Mahdi MOSLEH

Najmeh HOSSEINPOUR

Mohammad KHEYRANDISH

Related Institution

College of Computer Science and Technology, Changchun University

School of Economics, Changchun University

School of Information Science and Technology, Northeast Normal University

Division of Engineering Science, University of Toronto, Ontario M5S2E8

School of Computer Science and Electronic Engineering, University of Essex, Colchester CO43SQ

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰