Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
复制标题
全异步随机坐标下降：并行性的严格下限实现线性加速
DOI：
10.1007/s10107-020-01552-8
复制
发表时间：
2020
影响因子：
2.7
通讯作者：
Tao, Yixin
中科院分区：
文献类型：
--
作者：
Cheung, Yun Kuen;Cole, Richard;Tao, Yixin
在实现线性加速的坐标下降异步实现中，我们寻求可行并行度的紧边界。研究了由光滑凸部分和可能非光滑可分凸部分组成的凸函数的异步坐标下降算法。与标准顺序随机梯度下降相比，我们量化了进度的不足。这导致了对部分异步环境下标准随机ACD的简单而严密的分析，推广和改进了先前工作的界限。我们还对一般异步环境进行了相当复杂的分析，其中唯一的约束是每次更新最多可以与其他更新重叠。获得线性加速的最大并行度的新下界是严密的，并且几乎是二次地改进了最佳先验界。
We seek tight bounds on the viable parallelism in asynchronous implementations of coordinate descent that achieves linear speedup. We focus on asynchronous coordinate descent (ACD) algorithms on convex functions which consist of the sum of a smooth convex part and a possibly non-smooth separable convex part. We quantify the shortfall in progress compared to the standard sequential stochastic gradient descent. This leads to a simple yet tight analysis of the standard stochastic ACD in a partially asynchronous environment, generalizing and improving the bounds in prior work. We also give a considerably more involved analysis for general asynchronous environments in which the only constraint is that each update can overlap with at mostqothers. The new lower bound on the maximum degree of parallelism attaining linear speedup is tight and improves the best prior bound almost quadratically.
登录
查看更多内容
并行随机异步坐标下降：可能并行性的严格界限
影响因子：
3.1
作者：
Cheung, Yun Kuen;Cole, Richard J.;Tao, Yixin
通讯作者：
Tao, Yixin
DOI：
10.1109/acc.2012.6315289
发表时间：
2012-06
期刊：
2012 American Control Conference (ACC)
影响因子：
--
作者：
Konstantinos I. Tsianos;M. Rabbat
通讯作者：
Konstantinos I. Tsianos;M. Rabbat
通过有界最佳响应实现快速负载平衡
DOI：
--
发表时间：
2008
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
B. Awerbuch;Y. Azar;R. Khandekar
通讯作者：
R. Khandekar
DOI：
--
发表时间：
2012
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Yun Kuen Cheung;R. Cole;Ashish Rastogi
通讯作者：
Ashish Rastogi
DOI：
10.4230/lipics.esa.2018.18
发表时间：
2018
期刊：
ArXiv
影响因子：
--
作者：
Yun Kuen Cheung;R. Cole
通讯作者：
R. Cole