English

# 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}}$.