Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism
Authors:
Preprint
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_{\max}/L_{\overline{\mathrm{res}}})$ processors, where $L_{\max}$ and $L_{\overline{\mathrm{res}}}$ are suitable Lipschitz parameters. This paper shows the bound is tight for almost all possible values of these parameters.
Keywords
All Related Versions
This publication has 2 references indexed in Scilit:
- Perturbed Iterate Analysis for Asynchronous Stochastic OptimizationSIAM Journal on Optimization, 2017
- Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence PropertiesSIAM Journal on Optimization, 2015