hide
Free keywords:
Mathematics, Optimization and Control, math.OC,Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
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}}$.
