Distributed block coordinate descent for minimizing partially separable functions

Jakub Mareček, Peter Richtarik*, Martin Takáč

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 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 - Jan 1 2015
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
CountryOman
CityMuscat
Period01/5/1401/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

  • Mathematics(all)

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

Cite this