Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup

• 成果类型: Article
• 署名作者: Cheung, Yun Kuen; Cole, Richard; Tao, Yixin
• 署名单位: Singapore University of Technology & Design; New York University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01552-8
• 发表日期: 2021
• 页码: 615-677
• 关键词: convergence

摘要

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.