English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism

MPS-Authors
/persons/resource/persons202384

Cheung,  Yun Kuen
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1811.05087.pdf
(Preprint), 211KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Cheung, Y. K., Cole, R., & Tao, Y. (2018). Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism. Retrieved from http://arxiv.org/abs/1811.05087.


Cite as: http://hdl.handle.net/21.11116/0000-0002-AAF2-D
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(\sqrt n/L_{\mathsf{res}})$ processors, where $L_{\mathsf{res}}$ is a suitable Lipschitz parameter. This paper shows the bound is tight for essentially all possible values of $L_{\mathsf{res}}$.