On the Complexity of Parallel Coordinate Descent
Rachael Tappenden Martin Takáč Peter Richtárik
Abstract
In this work we study the parallel coordinate descent method (PCDM) proposed by Richtárik and Takáč [26] for minimizing a regularized convex function. We adopt elements from the work of Lu and Xiao [39], and combine them with several new insights, to obtain sharper iteration complexity results for PCDM than those presented in [26]. Moreover, we show that PCDM is monotonic in expectation, which was not confirmed in [26], and we also derive the first high probability iteration complexity result where the initial levelset is unbounded.
中文速览
并行坐标下降法（Parallel Coordinate Descent Method, PCDM）是求解大规模正则化凸优化问题的重要算法，但已有理论分析存在收敛性界不够紧、需要额外单调性检验、高概率结果依赖有界水平集等局限。本文通过引入 Lu 和 Xiao 的技术框架并结合多项新分析，系统改进了 PCDM 的理论保障：证明了算法在期望意义下天然具有单调性，无需原先的单调性判断步骤；首次在初始水平集无界的条件下建立了高概率迭代复杂度界；并在凸与强凸两种情形下均获得了比已有结果更紧的收敛速率和迭代复杂度。这些改进不仅让 PCDM 的算法实现更简洁，也为其在十亿维规模实际问题上的应用提供了更坚实的理论支撑。
原文 arXiv:1503.03033;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1503.03033v1