面向真实世界研究中非凸非平滑问题的具有时间扰动的块坐标下降法

刘睿; 孙唯楚; 侯涛; 胡春宏; 乔林波

doi:10.1631/FITEE.1900341

Your Location：

Home >

Browse articles >

面向真实世界研究中非凸非平滑问题的具有时间扰动的块坐标下降法

常规文章 | Updated：2022-05-19

- 面向真实世界研究中非凸非平滑问题的具有时间扰动的块坐标下降法
- Block coordinate descent with time perturbation for nonconvex nonsmooth problems in real-world studies
- 信息与电子工程前沿（英文） 2019年20卷第10期页码：1390-1403
- Affiliations：
  
  Department of Oncology, The Second Xiangya Hospital of Central South University, Changsha 410011, China
  First Clinical Medical College, University of South China, Hengyang 421001, China
  College of Computer, National University of Defense Technology, Changsha 410073, China
- Author bio：
  
  [ "Rui LIU, E-mail: liuruirui@csu.edu.cn" ]
  [ "Wei-chu SUN, E-mail: smsysun@foxmail.com" ]
  [ "Tao HOU, E-mail:houtao@csu.edu.cn" ]
  Chun-hong HU, E-mail: huchunhong@csu.edu.cn
  [ "Lin-bo QIAO, E-mail: qiao.linbo@nudt.edu.cn" ]
- Funds：
  
  Project supported by the National Key R&D Program of China (No. 2018YFB2101100) and the National Natural Science Foundation of China (Nos. 61806216 and 61702533)
- DOI：10.1631/FITEE.1900341
  中图分类号： TP391
- 收稿：2019-07-09，
  
  修回：2019-10-25，
  
  纸质出版：2019-10
- Accepted：
Scan QR Code
刘睿, 孙唯楚, 侯涛, 等. 面向真实世界研究中非凸非平滑问题的具有时间扰动的块坐标下降法[J]. 信息与电子工程前沿（英文）, 2019,20(10):1390-1403.

Rui LIU, Wei-chu SUN, Tao HOU, et al. Block coordinate descent with time perturbation for nonconvex nonsmooth problems in real-world studies[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(10): 1390-1403.
刘睿, 孙唯楚, 侯涛, 等. 面向真实世界研究中非凸非平滑问题的具有时间扰动的块坐标下降法[J]. 信息与电子工程前沿（英文）, 2019,20(10):1390-1403. DOI： 10.1631/FITEE.1900341.

Rui LIU, Wei-chu SUN, Tao HOU, et al. Block coordinate descent with time perturbation for nonconvex nonsmooth problems in real-world studies[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(10): 1390-1403. DOI： 10.1631/FITEE.1900341.

摘要

真实世界研究的大数据时代已经来临；这个时代将极大促进医学发展，尤其是肿瘤学。然而，鉴于大规模数据量的增加以及求解的目标问题具有非凸非平滑等不易求解的函数性质，传统机器学习方法不能很好解决这类新问题。我们的目标是求解一个带不等式约束的优化问题，该优化问题是由一个平滑非线性函数与大量块变量可分的非凸非平滑目标函数组合相加而得。提出一种新的并行一阶优化方法，称为带时间扰动的异步块坐标下降法（asynchronous block coordinate descent with time perturbation，ATP）。该方法采用一种从鞍点和次优局部点逃脱的时间扰动技术。通过分析收敛性和迭代复杂度特性，介绍了该方法的详细内容。针对真实世界研究机器学习问题的实验验证了本文所提方法的有效性。实验结果表明，时间扰动使ATP能从鞍点和次优点逃脱；采用异步块坐标下降法为处理具有不等式约束的非凸优化问题提供了一种可行方法。在共享内存多核平台上异步并行的实现，表明该算法具有很强可扩展性。

Abstract

The era of big data in healthcare is here

and this era will significantly improve medicine and especially oncology. However

traditional machine learning algorithms need to be promoted to solve such large-scale real-world problems due to a large amount of data that needs to be analyzed and the difficulty in solving problems with nonconvex nonlinear settings. We aim to minimize the composite of a smooth nonlinear function and a block-separable nonconvex function on a large number of block variables with inequality constraints. We propose a novel parallel first-order optimization method

called asynchronous block coordinate descent with time perturbation (ATP)

which adopts a time perturbation technique that escapes from saddle points and sub-optimal local points. The details of the proposed method are presented with analyses of convergence and iteration complexity properties. Experiments conducted on real-world machine learning problems validate the efficacy of our proposed method. The experimental results demonstrate that time perturbation enables ATP to escape from saddle points and sub-optimal points

providing a promising way to handle nonconvex optimization problems with inequality constraints employing asynchronous block coordinate descent. The asynchronous parallel implementation on shared memory multi-core platforms indicates that the proposed algorithm

ATP

has strong scalability.

关键词

Keywords

references

A Anandkumar , , , R Ge . . Efficient approaches for escaping higher order saddle points in non-convex optimization . . Proc 29 th Annual Conf on Learning Theory , , 2016 . . p.81 - - 102 . . . .

DP Bertsekas , , , JN Tsitsiklis . . Parallel and Distributed Computation: Numerical Methods . . Prentice Hall, Englewood Cliffs, NJ, USA , , 1989 . . .

D Bertsimas , , , MV Bjarnadóttir , , , MA Kane , , , 等 . . Algorithmic prediction of health-care costs . . Oper Res , , 2008 . . 56 ( ( 6 ): ): 1382 - - 1392 . . DOI: 10.1287/opre.1080.0619 http://doi.org/10.1287/opre.1080.0619 . .

L Cannelli , , , F Facchinei , , , V Kungurtsev , , , 等 . . Asynchronous parallel algorithms for nonconvex optimization , , 2018 . . https://arxiv.org/abs/1607.04818 https://arxiv.org/abs/1607.04818 , , . .

L Dagum , , , R Menon . . OpenMP: an industry standard API for shared-memory programming . . IEEE Comput Sci Eng , , 1998 . . 5 ( ( 1 ): ): 46 - - 55 . . DOI: 10.1109/99.660313 http://doi.org/10.1109/99.660313 . .

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 . .

J Friedman , , , T Hastie , , , R Tibshirani . . The Elements of Statistical Learning . . pringer, Berlin, Germany , , 2001 . . .

R Ge , , , FR Huang , , , C Jin , , , 等 . . Escaping from saddle points—online stochastic gradient for tensor decomposition . . Proc 28 th Conf on Learning Theory , , 2015 . . p.797 - - 842 . . . .

G Guennebaud , , , B Jacob . . Eigen v3 , , 2010 . . http://eigen.tuxfamily.org http://eigen.tuxfamily.org , , . .

E Hazan , , , KY Levy , , , S Shalev-Shwartz . . On graduated optimization for stochastic non-convex problems . . Proc 33rd Int Conf on Machine Learning , , 2016 . . p.1833 - - 1841 . . . .

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 . .

GM James , , , C Paulson , , , P Rusmevichientong . . The Constrained Lasso . . Working Paper, University of Southern California, Los Angeles, California, USA , , 2012 . . .

B Jiang , , , TY Lin , , , SQ Ma , , , 等 . . Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis . . Comput Optim Appl , , 2019 . . 72 ( ( 1 ): ): 115 - - 157 . . DOI: 10.1007/s10589-018-0034-y http://doi.org/10.1007/s10589-018-0034-y . .

C Jin , , , R Ge , , , P Netrapalli , , , 等 . . How to escape saddle points efficiently . . Proc 34 th Int Conf on Machine Learning , , 2017 . . p.1724 - - 1732 . . . .

S Khozin , , , GM Blumenthal , , , R Pazdur . . Real-world data for clinical evidence generation in oncology . . J Nat Cancer Inst , , 2017 . . 109 ( ( 11 ): ): Article djx187 DOI: 10.1093/jnci/djx187 http://doi.org/10.1093/jnci/djx187 . .

D Li , , , Z Lai , , , K Ge , , , 等 . . HPDL: towards a general framework for high-performance distributed deep learning . . Proc 39 th IEEE Int Conf on Distributed Computing Systems , , 2019 . . p.1742 - - 1753 . . . .

JQ Li , , , A Vachani , , , A Epstein , , , 等 . . A doubly robust approach for cost-effectiveness estimation from observational data . . Stat Methods Med Res , , 2018 . . 27 ( ( 10 ): ): 3126 - - 3138 . . DOI: 10.1177/0962280217693262 http://doi.org/10.1177/0962280217693262 . .

R Liu . . Asynchronous block coordinate descent method for large-scale nonconvex problem in real world study . . Proc IEEE 21 st Int Conf on High Performance Computing and Communications, jointly with IEEE 17th Int Conf on Smart City and IEEE 5 th Int Conf on Data Science and Systems , , 2019 . . p.2033 - - 2038 . . DOI: 10.1109/HPCC/SmartCity/DSS.2019.00281 http://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00281 . .

Y Nesterov . . Efficiency of coordinate descent methods on huge-scale optimization problems . . SIAM J Optim , , 2012 . . 22 ( ( 2 ): ): 341 - - 362 . . DOI: 10.1137/100802001 http://doi.org/10.1137/100802001 . .

Y Nesterov , , , A Nemirovskii . . Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, USA , , 1994 . . DOI: 10.1137/1.9781611970791 http://doi.org/10.1137/1.9781611970791 . .

DP Palomar , , , M Chiang . . A tutorial on decomposition methods for network utility maximization . . IEEE J Sel Areas Commun , , 2006 . . 24 ( ( 8 ): ): 1439 - - 1451 . . DOI: 10.1109/JSAC.2006.879350 http://doi.org/10.1109/JSAC.2006.879350 . .

ZM Peng , , , YY Xu , , , M Yan , , , 等 . . On the convergence of asynchronous parallel iteration with unbounded delays . . J Oper Res Soc China , , 2019 . . 7 ( ( 1 ): ): 5 - - 42 . . DOI: 10.1007/s40305-017-0183-1 http://doi.org/10.1007/s40305-017-0183-1 . .

LB Qiao , , , BF Zhang , , , JS Su , , , 等 . . Linearized alternating direction method of multipliers for constrained nonconvex regularized optimization . . Proc 8 th Asian Conf on Machine Learning , , 2016a . . p.97 - - 109 . . . .

LB Qiao , , , TY Lin , , , YG Jiang , , , 等 . . On stochastic primal-dual hybrid gradient approach for compositely regularized minimization . . Proc 22 nd European Conf on Artificial Intelligence , , 2016b . . p.167 - - 174 . . DOI: 10.3233/978-1-61499-672-9-167 http://doi.org/10.3233/978-1-61499-672-9-167 . .

LB Qiao , , , BF Zhang , , , XC Lu , , , 等 . . Adaptive linearized alternating direction method of multipliers for non-convex compositely regularized optimization problems . . Tsinghua Sci Technol , , 2017 . . 22 ( ( 3 ): ): 328 - - 341 . . DOI: 10.23919/TST.2017.7914204 http://doi.org/10.23919/TST.2017.7914204 . .

LB Qiao , , , TY Lin , , , Q Qin , , , 等 . . On the iteration complexity analysis of stochastic primal-dual hybrid gradient approach with high probability . . Neurocomputing , , 2018 . . 307 78 - - 90 . . DOI: 10.1016/j.neucom.2018.03.066 http://doi.org/10.1016/j.neucom.2018.03.066 . .

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

RT Rockafellar , , , RJB Wets . . Variational Analysis , , : : New York, USA Springer , , 2009 . . .

L Shen , , , W Liu , , , G Yuan , , , 等 . . GSOS: Gauss-Seidel operator splitting algorithm for multi-term nonsmooth convex composite optimization . . Proc 34 th Int Conf on Machine Learning , , 2017 . . p.3125 - - 3134 . . . .

L Shen , , , P Sun , , , YT Wang , , , 等 . . An algorithmic framework of variable metric over-relaxed hybrid proximal extra-gradient method , , 2018 . . https://arxiv.org/abs/1805.06137 https://arxiv.org/abs/1805.06137 , , . .

MZ Sun , , , Y Jiang , , , C Sun , , , 等 . . The associations between smoking and obesity in northeast China: a quantile regression analysis . . Sci Rep , , 2019 . . 9 Article 3732 DOI: 10.1038/s41598-019-39425-6 http://doi.org/10.1038/s41598-019-39425-6 . .

T Sun , , , R Hannah , , , W Yin , , , 等 . . Asynchronous coordinate descent under more realistic assumptions . . Proc Advances in Neural Information Processing Systems , , 2017 . . p.6182 - - 6190 . . . .

X Wang , , , SQ Ma , , , D Goldfarb , , , 等 . . Stochastic quasiNewton methods for nonconvex stochastic optimization . . SIAM J Optim , , 2017 . . 27 ( ( 2 ): ): 927 - - 956 . . DOI: 10.1137/15M1053141 http://doi.org/10.1137/15M1053141 . .

Y Wang , , , W Yin , , , J Zeng . . Global convergence of ADMM in nonconvex nonsmooth optimization . . J Sci Comput , , 2019 . . 78 ( ( 1 ): ): 29 - - 63 . . DOI: 10.1007/s10915-018-0757-z http://doi.org/10.1007/s10915-018-0757-z . .

L Xiao , , , M Johansson , , , SP Boyd . . Simultaneous routing and resource allocation via dual decomposition . . IEEE Trans Commun , , 2004 . . 52 ( ( 7 ): ): 1136 - - 1144 . . DOI: 10.1109/TCOMM.2004.831346 http://doi.org/10.1109/TCOMM.2004.831346 . .

YY Xu . . Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs , , 2019 . . https://arxiv.org/abs/1705.06391 https://arxiv.org/abs/1705.06391 , , . .

YY Xu , , , W Yin . . A globally convergent algorithm for nonconvex optimization based on block coordinate update . . J Sci Comput , , 2017 . . 72 ( ( 2 ): ): 700 - - 734 . . DOI: 10.1007/s10915-017-0376-0 http://doi.org/10.1007/s10915-017-0376-0 . .

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 . .

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

X Zhang , , , J Liu , , , ZY Zhu . . Taming convergence for asynchronous stochastic gradient descent with unbounded delay in non-convex learning , , 2018 . . https://arxiv.org/abs/1805.09470 https://arxiv.org/abs/1805.09470 , , . .

FY Zou , , , L Shen , , , ZQ Jie , , , 等 . . A sufficient condition for convergences of Adam and RMSProp . . Proc IEEE Conf on Computer Vision and Pattern Recognition , , 2018 . . p.11127 - - 11135 . . https://arxiv.org/abs/1811.09358 https://arxiv.org/abs/1811.09358 , , . .

FY Zou , , , L Shen , , , ZQ Jie , , , 等 . . Weighted AdaGrad with unified momentum , , 2019 . . https://arxiv.org/abs/1808.03408 https://arxiv.org/abs/1808.03408 , , . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据