An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
\nameJi Liu \nameStephen J. Wright \addrDepartment of Computer Sciences, University of Wisconsin-Madison, Madison, WI 53706 \nameChristopher Ré \addrDepartment of Computer Science, Stanford University, Stanford, CA 94305 \nameVictor Bittorf \addrCloudera, Inc., Palo Alto, CA 94304 \nameSrikrishna Sridhar \addrGraphLab Inc., Seattle, WA 98103
Abstract
We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential 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/2})$ in unconstrained optimization and $O(n^{1/4})$ in the separable-constrained case, where $n$ is the number of variables. We describe results from implementation on 40-core processors.
中文速览
异步并行随机坐标下降（Asynchronous Stochastic Coordinate Descent，AsySCD）是一种让多核处理器无需等待彼此同步、各自独立更新变量分量的优化算法，但现有理论对其收敛速度和并行加速条件的分析还不够完善。本文提出并严格分析了 AsySCD 算法：在"本质强凸（essential strong convexity）"条件下可达线性收敛，对一般凸函数则有 1/K 的次线性收敛保证；同时给出了实现近线性加速的充分条件——处理器数量在无约束情形下不超过 O(n^{1/2})、在可分离约束情形下不超过 O(n^{1/4})（n 为变量维数）。作者在 40 核 Intel Xeon 机器上的实验验证了理论预测，实际加速比接近线性。这项工作为大规模机器学习问题（如支持向量机、LASSO、逻辑回归）的高效并行求解提供了坚实的理论依据和实用算法框架。
原文 arXiv:1311.1873;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1311.1873v3