Parallel coordinate descent methods for big data optimization

被引:206
作者
Richtarik, Peter [1 ]
Takac, Martin [1 ]
机构
[1] Univ Edinburgh, Sch Math, Edinburgh, Midlothian, Scotland
基金
英国工程与自然科学研究理事会;
关键词
Parallel coordinate descent; Big data optimization; Partial separability; Huge-scale optimization; Iteration complexity; CONVERGENCE; ALGORITHM;
D O I
10.1007/s10107-015-0901-6
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring to the number of iterations needed to approximately solve the problem with high probability, is a simple expression depending on the number of parallel processors and a natural and easily computable measure of separability of the smooth component of the objective function. In the worst case, when no degree of separability is present, there may be no speedup; in the best case, when the problem is separable, the speedup is equal to the number of processors. Our analysis also works in the mode when the number of blocks being updated at each iteration is random, which allows for modeling situations with busy or unreliable processors. We show that our algorithm is able to solve a LASSO problem involving a matrix with 20 billion nonzeros in 2 h on a large memory node with 24 cores.
引用
收藏
页码:433 / 484
页数:52
相关论文
共 29 条
[1]  
[Anonymous], 2013, ARXIV13095885
[2]  
[Anonymous], ICML
[3]  
[Anonymous], 2011, NIPS
[4]  
[Anonymous], 2011, NEURIPS
[5]  
[Anonymous], 2013, ARXIV PREPRINT ARXIV
[6]  
[Anonymous], 2012, TECHNICAL REPORT
[7]  
[Anonymous], 2013, ICML
[8]   Randomized Methods for Linear Constraints: Convergence Rates and Conditioning [J].
Leventhal, D. ;
Lewis, A. S. .
MATHEMATICS OF OPERATIONS RESEARCH, 2010, 35 (03) :641-654
[9]   COORDINATE DESCENT OPTIMIZATION FOR l1 MINIMIZATION WITH APPLICATION TO COMPRESSED SENSING; A GREEDY ALGORITHM [J].
Li, Yingying ;
Osher, Stanley .
INVERSE PROBLEMS AND IMAGING, 2009, 3 (03) :487-503
[10]   A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints [J].
Necoara, Ion ;
Patrascu, Andrei .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2014, 57 (02) :307-337