Iteration complexity analysis of block coordinate descent methods
Iteration complexity analysis of block coordinate descent methods
复制标题
块坐标下降法的迭代复杂度分析
DOI：
10.1007/s10107-016-1057-8
复制
发表时间：
2017-05-01
影响因子：
2.7
通讯作者：
Luo, Zhi-Quan
中科院分区：
文献类型：
--
作者：
Hong, Mingyi;Wang, Xiangfeng;Luo, Zhi-Quan
在本文中，我们提供了一个统一的迭代复杂性分析的一般块坐标下降的方法，包括流行的方法，如块坐标梯度下降和块坐标邻近梯度，在各种不同的坐标更新规则。我们统一这些算法下的所谓的块连续上限最小化（BSUM）框架，并表明，对于广泛的一类多块非光滑凸问题，所有算法所涵盖的BSUM框架实现了全球次线性迭代复杂性，其中的迭代指数。此外，对于块坐标极小化问题，即每个块都精确极小化的情形，在没有每块强凸性假设的情况下，我们建立了O（1/r）的次线性收敛速度。
In this paper, we provide a unified iteration complexity analysis for a family of general block coordinate descent methods, covering popular methods such as the block coordinate gradient descent and the block coordinate proximal gradient, under various different coordinate update rules. We unify these algorithms under the so-called block successive upper-bound minimization (BSUM) framework, and show that for a broad class of multi-block nonsmooth convex problems, all algorithms covered by the BSUM framework achieve a global sublinear iteration complexity of, whereris the iteration index. Moreover, for the case of block coordinate minimization where each block is minimized exactly, we establish the sublinear convergence rate ofO(1/r) without per block strong convexity assumption.