Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism
研究了异步并行随机坐标下降的线性加速条件，证明了已知处理器数量上界对于几乎所有参数值都是紧的。
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(L_{\max}\sqrt n/L_{\overline{{res}}})$ processors, where $L_{\max}$ and $L_{\overline{{res}}}$ are suitable Lipschitz parameters. This paper shows the bound is tight for almost all possible values of these parameters.