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 proceedingConference contributionpeer-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 languageEnglish (US)
Title of host publicationNumerical Analysis and Optimization, NAO-III 2014
EditorsMehiddin Al-Baali, Lucio Grandinetti, Anton Purnama
PublisherSpringer New York LLC
Pages261-288
Number of pages28
ISBN (Print)9783319176888
DOIs
StatePublished - 2015
Externally publishedYes
Event3rd International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOIII-2014 - Muscat, Oman
Duration: Jan 5 2014Jan 9 2014

Publication series

NameSpringer Proceedings in Mathematics and Statistics
Volume134
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017

Other

Other3rd International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOIII-2014
Country/TerritoryOman
CityMuscat
Period01/5/1401/9/14

Bibliographical note

Funding Information:
The first author was supported by EPSRC grant EP/I017127/1 (Mathematics for Vast Digital Resources) in 2012 and by the EU FP7 INSIGHT project (318225) subsequently. The second author was supported by EPSRC grant EP/I017127/1. The third author was supported by the Centre for Numerical Algorithms and Intelligent Software, funded by EPSRC grant EP/G036136/1 and the Scottish Funding Council.

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

Fingerprint

Dive into the research topics of 'Distributed block coordinate descent for minimizing partially separable functions'. Together they form a unique fingerprint.

Cite this