Asynchronous Block Coordinate Descent Method for Large-Scale Nonconvex Problem in Real World Study

摘要

Here comes the era of big data in healthcare, and this era will transform medicine and especially oncology. In the last decade, there has been a growing interest in the potential benefits and the relevance of real world studies (RWS) with to the rapid development of data mining algorithms, as well as large-scale accumulated real world datasets. However, it is beyond the ability of traditional data mining algorithms to solve such large-scale RWS problems due to the large amount of data need to be processed and the difficulty in the problems solving, especially the nonconvex optimization problems. In many cases for these nonconvex problems, the goal is to find a reasonable local minimum, and the main concern is that the iterative updates are easily trapped in saddle points or bad local optima points. In this paper, we aim at minimizing the sum of a smooth nonlinear function and a block-separable nonconvex function involving a large number of block variables subjected to inequality constraints, which covers a wide range of interesting applications appearing in distributed optimization, statistics learning, etc. However, solving such a nonconvex nonlinear optimization problem associated with inequality constraints remains as a challenging task. This is because: 1) it is still an open problem about how to escape from saddle points and bad local optima points using a block coordinate descent method to deal with the nonconvex nonlinear optimization functions; 2) it can be extremely expensive to compute the entire block variables when the problem scale is large. Therefore, we propose a novel parallel first-order optimization method, called as Asynchronous block coordinate descent with Time Perturbation (ATP), which utilizing the time perturbation technique that escapes from saddle points and local optima points. We present a randomized block variable selection rule of the proposed method, as well as the iteration complexity. Experiments conducted on typical machine learning problems in RWS, i.e., folded concave linear regression, validate the efficacy of our optimization method. In particular, the experiment results demonstrate that time perturbation could greatly help the proposed algorithm escape from saddle points and local optima in the nonconvex part, which provides a promising way to tackle nonconvex optimization problems employing block coordinate descent.