CLC number: TP391
On-line Access: 2020-04-21
Received: 2018-09-14
Revision Accepted: 2018-12-08
Crosschecked: 2019-08-12
Cited: 0
Clicked: 6016
Lei Guan, Tao Sun, Lin-bo Qiao, Zhi-hui Yang, Dong-sheng Li, Ke-shi Ge, Xi-cheng Lu. An efficient parallel and distributed solution to nonconvex penalized linear SVMs[J]. Frontiers of Information Technology & Electronic Engineering,in press.https://doi.org/10.1631/FITEE.1800566 @article{title="An efficient parallel and distributed solution to nonconvex penalized linear SVMs", %0 Journal Article TY - JOUR
一种有效求解非凸正则化线性支持向量机的并行与分布式方法关磊1,孙涛1,乔林波1,杨智慧2,3,李东升1,葛可适1,卢锡城1 1国防科技大学计算机学院,中国长沙市,410073 2复旦大学计算机科学技术学院,中国上海市,201203 3上海市数据科学重点实验室,中国上海市,201203 摘要:支持向量机(SVM)被视为线性分类的有力工具。与可以产生稀疏效果的非凸惩罚项组合时,SVM能同时执行分类和变量选择。然而,由于其不可微、非凸和非平滑特性,非凸正则化SVM通常难以有效求得全局最优解。已有针对非凸正则化SVM的求解方案通常以串行方式求解,因而无法充分利用现代多核机器的并行处理能力。另一方面,现实世界中数据多以分布式方式存储,迫切需要一种并行与分布式方法求解非凸正则化SVM问题。为应对这一挑战,本文提出一种基于交替方向乘子法(ADMM)的并行算法高效求解非凸正则化SVM问题。采用有效技术降低并行算法的计算与同步开销。时间复杂度分析证明所提并行算法具有低复杂度。此外,该并行算法能保证收敛性。在LIBSVM数据集上的实验证明了所提并行算法的有效性。 关键词组: Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article
Reference[1]Allen-Zhu Z, Hazan E, 2016. Variance reduction for faster non-convex optimization. Proc 33rd Int Conf on Machine Learning, p.699-707. [2]Boyd S, Parikh N, Chu E, et al., 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn, 3(1):1-122. [3]Cand‘es EJ, Wakin MB, Boyd SP, 2008. Enhancing sparsity by reweighted ℓ1 minimization. J Fourier Anal Appl, 14(5-6):877-905. [4]Daneshmand A, Facchinei F, Kungurtsev V, et al., 2015. Hybrid random/deterministic parallel algorithms for convex and nonconvex big data optimization. IEEE Trans Signal Process, 63(15):3914-3929. [5]di Lorenzo P, Scutari G, 2015. Distributed nonconvex optimization over networks. IEEE 6th Int Workshop on Computational Advances in Multi-sensor Adaptive Processing, p.229-232. [6]Facchinei F, Scutari G, Sagratella S, 2015. Parallel selective algorithms for nonconvex big data optimization. IEEE Trans Signal Process, 63(7):1874-1889. [7]Fan JQ, Li RZ, 2001. Variable selection via nonconcave penalized likelihood and its oracle properties. J Am Stat Assoc, 96(456):1348-1360. [8]Gong PH, Zhang CS, Lu ZS, et al., 2013. A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems. Proc Int Conf on Machine Learning, p.37-45. [9]Guan L, Qiao LB, Li DS, et al., 2018. An efficient ADMM-based algorithm to nonconvex penalized support vector machines. Proc 18th IEEE Int Conf on Data Mining, p.1209-1216. [10]Hong MY, Luo ZQ, Razaviyayn M, 2016. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J Optim, 26(1):337-364. [11]Laporte L, Flamary R, Canu S, et al., 2014. Nonconvex regularizations for feature selection in ranking with sparse SVM. IEEE Trans Neur Netw Learn Syst, 25(6):1118-1130. [12]Liu HC, Yao T, Li RZ, 2016. Global solutions to folded concave penalized nonconvex learning. Ann Stat, 44(2):629-659. [13]Mazumder R, Friedman JH, Hastie T, 2011. SparseNet: coordinate descent with nonconvex penalties. J Am Stat Assoc, 106(495):1125-1138. [14]Ochs P, Chen YJ, Brox T, et al., 2014. iPiano: inertial proximal algorithm for nonconvex optimization. SIAM J Imag Sci, 7(2):1388-1419. [15]Razaviyayn M, Hong MY, Luo ZQ, et al., 2014. Parallel successive convex approximation for nonsmooth nonconvex optimization. Proc 27th Int Conf on Neural Information Processing Systems, p.1440-1448. [16]Reddi SJ, Sra S, Poczos B, et al., 2016. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Proc 30th Conf on Neural Information Processing Systems, p.1145-1153. [17]Scutari G, Facchinei F, Lampariello L, 2017. Parallel and distributed methods for constrained nonconvex optimization—Part I: theory. IEEE Trans Signal Process, 65(8):1929-1944. [18]Sherman J, Morrison WJ, 1950. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann Math Stat, 21(1):124-127. [19]Sun T, Jiang H, Cheng LZ, et al., 2017a. A convergence frame for inexact nonconvex and nonsmooth algorithms and its applications to several iterations. https://arxiv.org/abs/1709.04072 [20]Sun T, Jiang H, Cheng LZ, 2017b. Iteratively linearized reweighted alternating direction method of multipliers for a class of nonconvex problems. https://arxiv.org/abs/1709.00483 [21]Sun T, Yin PH, Cheng LZ, et al., 2018a. Alternating direction method of multipliers with difference of convex functions. Adv Comput Math, 44(3):723-744. [22]Sun T, Yin PH, Li DS, et al., 2018b. Non-ergodic convergence analysis of heavy-ball algorithms. https://arxiv.org/abs/1811.01777v2 [23]Sun Y, Scutari G, Palomar D, 2016. Distributed nonconvex multiagent optimization over time-varying networks. Proc 50th Asilomar Conf on Signals, Systems and Computers, p.788-794. [24]Wang Y, Yin WT, Zeng JS, 2015. Global convergence of ADMM in nonconvex nonsmooth optimization. https://arxiv.org/abs/1511.06324 [25]Zhang CH, 2010. Nearly unbiased variable selection under minimax concave penalty. Ann Stat, 38(2):894-942. [26]Zhang HH, Ahn J, Lin XD, et al., 2006. Gene selection using support vector machines with non-convex penalty. Bioinformatics, 22(1):88-95. [27]Zhang SB, Qian H, Gong XJ, 2016. An alternating proximal splitting method with global convergence for nonconvex structured sparsity optimization. Proc 30th AAAI Conf on Artificial Intelligence, p.2330-2336. [28]Zhang T, 2010. Analysis of multi-stage convex relaxation for sparse regularization. J Mach Learn Res, 11:1081-1107. [29]Zhang X, Wu YC, Wang L, et al., 2016. Variable selection for support vector machines in moderately high dimensions. J R Stat Soc Ser B, 78(1):53-76. [30]Zhang YM, Li DS, Guo CX, et al., 2017. CubicRing: exploiting network proximity for distributed in-memory key-value store. IEEE/ACM Trans Netw, 25(4):2040-2053. Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou
310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE |
Open peer comments: Debate/Discuss/Question/Opinion
<1>