Parallel stochastic asynchronous coordinate descent: Tight bounds on the possible parallelism

Yun Kuen Cheung, Richard J. Cole, Yixin Tao

Research output: Contribution to journalArticlepeer-review

Abstract

Several works have shown linear speedup is achieved by an asynchronous parallel implementation of stochastic coordinate descent so long as there is not too much parallelism. More specifically, it is known that if all updates are of similar duration, then linear speedup is possible with up to \Theta (Lmax\surd n/Lres) processors, where Lmax and Lres are suitable Lipschitz parameters. This paper shows the bound is tight for almost all possible values of these parameters.

Original languageEnglish (US)
Pages (from-to)448-460
Number of pages13
JournalSIAM Journal on Optimization
Volume31
Issue number1
DOIs
StatePublished - Feb 2021

Keywords

  • Parallelism bound
  • Stochastic asynchronous coordinate descent

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Parallel stochastic asynchronous coordinate descent: Tight bounds on the possible parallelism'. Together they form a unique fingerprint.

Cite this