TY - GEN

T1 - Distributed block coordinate descent for minimizing partially separable functions

AU - Mareček, Jakub

AU - Richtarik, Peter

AU - Takáč, Martin

PY - 2015/1/1

Y1 - 2015/1/1

N2 - A distributed randomized block coordinate descent method for minimizing a convex function of a huge number of variables is proposed. The complexity of the method is analyzed under the assumption that the smooth part of the objective function is partially block separable. The number of iterations required is bounded by a function of the error and the degree of separability, which extends the results in Richtárik and Takác (Parallel Coordinate Descent Methods for Big Data Optimization, Mathematical Programming, DOI:10.1007/s10107-015-0901-6) to a distributed environment. Several approaches to the distribution and synchronization of the computation across a cluster of multi-core computer are described and promising computational results are provided.

AB - A distributed randomized block coordinate descent method for minimizing a convex function of a huge number of variables is proposed. The complexity of the method is analyzed under the assumption that the smooth part of the objective function is partially block separable. The number of iterations required is bounded by a function of the error and the degree of separability, which extends the results in Richtárik and Takác (Parallel Coordinate Descent Methods for Big Data Optimization, Mathematical Programming, DOI:10.1007/s10107-015-0901-6) to a distributed environment. Several approaches to the distribution and synchronization of the computation across a cluster of multi-core computer are described and promising computational results are provided.

KW - Big data optimization

KW - Communication complexity

KW - Composite objective

KW - Convex optimization

KW - Distributed coordinate descent

KW - Empirical risk minimization

KW - Expected separable over-approximation

KW - Huge-scale optimization

KW - Iteration complexity

KW - Partial separability

KW - Support vector machine

UR - http://www.scopus.com/inward/record.url?scp=84947061596&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-17689-5_11

DO - 10.1007/978-3-319-17689-5_11

M3 - Conference contribution

AN - SCOPUS:84947061596

SN - 9783319176888

T3 - Springer Proceedings in Mathematics and Statistics

SP - 261

EP - 288

BT - Numerical Analysis and Optimization, NAO-III 2014

A2 - Al-Baali, Mehiddin

A2 - Grandinetti, Lucio

A2 - Purnama, Anton

PB - Springer New York LLC

T2 - 3rd International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOIII-2014

Y2 - 5 January 2014 through 9 January 2014

ER -