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 | |
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 |
Bibliographical note
Publisher Copyright:© Springer International Publishing Switzerland 2015.
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