Distributed block coordinate descent for minimizing partially separable functions

Jakub Mareček; Peter Richtárik; Martin Takáč

doi:10.1007/978-3-319-17689-5_11

Distributed block coordinate descent for minimizing partially separable functions

Jakub Mareček, Peter Richtárik^*, Martin Takáč

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

20 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Numerical Analysis and Optimization, NAO-III 2014
Editors	Mehiddin Al-Baali, Lucio Grandinetti, Anton Purnama
Publisher	Springer New York LLC
Pages	261-288
Number of pages	28
ISBN (Print)	9783319176888
DOIs	https://doi.org/10.1007/978-3-319-17689-5_11
State	Published - 2015
Externally published	Yes
Event	3rd International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOIII-2014 - Muscat, Oman Duration: Jan 5 2014 → Jan 9 2014

Publication series

Name	Springer Proceedings in Mathematics and Statistics
Volume	134
ISSN (Print)	2194-1009
ISSN (Electronic)	2194-1017

Other

Other	3rd International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOIII-2014
Country/Territory	Oman
City	Muscat
Period	01/5/14 → 01/9/14

Keywords

Big data optimization
Communication complexity
Composite objective
Convex optimization
Distributed coordinate descent
Empirical risk minimization
Expected separable over-approximation
Huge-scale optimization
Iteration complexity
Partial separability
Support vector machine

ASJC Scopus subject areas

General Mathematics

Access to Document

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

Cite this

Mareček, J., Richtárik, P., & Takáč, M. (2015). Distributed block coordinate descent for minimizing partially separable functions. In M. Al-Baali, L. Grandinetti, & A. Purnama (Eds.), Numerical Analysis and Optimization, NAO-III 2014 (pp. 261-288). (Springer Proceedings in Mathematics and Statistics; Vol. 134). Springer New York LLC. https://doi.org/10.1007/978-3-319-17689-5_11

@inproceedings{8384fbf05f1f4e719761f48ea27c8803,

title = "Distributed block coordinate descent for minimizing partially separable functions",

abstract = "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{\'a}rik and Tak{\'a}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.",

keywords = "Big data optimization, Communication complexity, Composite objective, Convex optimization, Distributed coordinate descent, Empirical risk minimization, Expected separable over-approximation, Huge-scale optimization, Iteration complexity, Partial separability, Support vector machine",

author = "Jakub Mare{\v c}ek and Peter Richt{\'a}rik and Martin Tak{\'a}{\v c}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 3rd International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOIII-2014 ; Conference date: 05-01-2014 Through 09-01-2014",

year = "2015",

doi = "10.1007/978-3-319-17689-5_11",

language = "English (US)",

isbn = "9783319176888",

series = "Springer Proceedings in Mathematics and Statistics",

publisher = "Springer New York LLC",

pages = "261--288",

editor = "Mehiddin Al-Baali and Lucio Grandinetti and Anton Purnama",

booktitle = "Numerical Analysis and Optimization, NAO-III 2014",

}

Mareček, J, Richtárik, P & Takáč, M 2015, Distributed block coordinate descent for minimizing partially separable functions. in M Al-Baali, L Grandinetti & A Purnama (eds), Numerical Analysis and Optimization, NAO-III 2014. Springer Proceedings in Mathematics and Statistics, vol. 134, Springer New York LLC, pp. 261-288, 3rd International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOIII-2014, Muscat, Oman, 01/5/14. https://doi.org/10.1007/978-3-319-17689-5_11

Distributed block coordinate descent for minimizing partially separable functions. / Mareček, Jakub; Richtárik, Peter; Takáč, Martin.
Numerical Analysis and Optimization, NAO-III 2014. ed. / Mehiddin Al-Baali; Lucio Grandinetti; Anton Purnama. Springer New York LLC, 2015. p. 261-288 (Springer Proceedings in Mathematics and Statistics; Vol. 134).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Distributed block coordinate descent for minimizing partially separable functions

AU - Mareček, Jakub

AU - Richtárik, Peter

AU - Takáč, Martin

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

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 -

Distributed block coordinate descent for minimizing partially separable functions

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this