Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
Ji Liu Department of Computer Sciences, University of Wisconsin-Madison, 1210 W. Dayton St., Madison, WI 53706-1685, US This author was supported in part by NSF Awards DMS-0914524 and DMS-1216318 and ONR Award N00014-13-1-0129. Stephen J. Wright Department of Computer Sciences, University of Wisconsin-Madison, 1210 W. Dayton St., Madison, WI 53706-1685, US This author was supported in part by NSF Awards DMS-0914524, DMS-1216318, and IIS-1447449, ONR Award N00014-13-1-0129, AFOSR Award FA9550-13-1-0138, and Subcontract 3F-30222 from Argonne National Laboratory.
Abstract
We describe an asynchronous parallel stochastic proximal coordinate descent algorithm for minimizing a composite objective function, which consists of a smooth convex function added to a separable convex function. In contrast to previous analyses, our model of asynchronous computation accounts for the fact that components of the unknown vector may be written by some cores simultaneously with being read by others. Despite the complications arising from this possibility, the method achieves a linear convergence rate on functions that satisfy an optimal strong convexity property and a sublinear rate ( $1/k$ ) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is $O(n^{1/4})$ . We describe results from implementation on ten cores of a multicore processor.
中文速览
大规模机器学习中的稀疏优化问题（如LASSO、逻辑回归）往往需要在多核处理器上高效求解，但现有异步并行算法普遍回避了一个现实问题：多个核心同时读写共享内存时，某个核心读到的向量可能是从未真正完整存在过的"混合版本"。本文提出了一种名为AsySPCD的异步随机近端坐标下降算法，首次在"不一致读取"模型下严格分析了这种混合读取带来的影响，从理论上证明：在满足最优强凸条件时算法以线性速率收敛，在一般凸函数上以1/k的次线性速率收敛，且当处理器数量不超过问题维度n的四次方根时可获得近线性加速比。在十核处理器上的实验验证了理论预测，表明该工作为多核异步优化提供了更贴近硬件实际、理论保障更完整的分析框架。
原文 arXiv:1403.3862;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1403.3862v2