@online{corr/abs-1811-05087,
TITLE = {Parallel Stochastic Asynchronous Coordinate Descent: {T}ight Bounds on the Possible Parallelism},
AUTHOR = {Cheung, Yun Kuen and Cole, Richard and Tao, Yixin},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1811.05087},
EPRINT = {1811.05087},
EPRINTTYPE = {arXiv},
YEAR = {2018},
MARGINALMARK = {$\bullet$},
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}}$.},
}