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 (Lmax\surd n/Lres) processors, where Lmax and Lres are suitable Lipschitz parameters. This paper shows the bound is tight for almost all possible values of these parameters.
- Parallelism bound
- Stochastic asynchronous coordinate descent
ASJC Scopus subject areas
- Theoretical Computer Science