Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup

Yun Kuen Cheung, Richard Cole, Yixin Tao

Research output: Contribution to journalArticlepeer-review

Abstract

We seek tight bounds on the viable parallelism in asynchronous implementations of coordinate descent that achieves linear speedup. We focus on asynchronous coordinate descent (ACD) algorithms on convex functions which consist of the sum of a smooth convex part and a possibly non-smooth separable convex part. We quantify the shortfall in progress compared to the standard sequential stochastic gradient descent. This leads to a simple yet tight analysis of the standard stochastic ACD in a partially asynchronous environment, generalizing and improving the bounds in prior work. We also give a considerably more involved analysis for general asynchronous environments in which the only constraint is that each update can overlap with at most q others. The new lower bound on the maximum degree of parallelism attaining linear speedup is tight and improves the best prior bound almost quadratically.

Original languageEnglish (US)
Pages (from-to)615-677
Number of pages63
JournalMathematical Programming
Volume190
Issue number1-2
DOIs
StatePublished - Nov 2021

Keywords

  • Amortized analysis
  • Asynchronous coordinate descent
  • Linear speedup
  • Stochastic coordinate descent

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup'. Together they form a unique fingerprint.

Cite this