In this paper, we provide a unified iteration complexity analysis for a
family of general block coordinate descent (BCD) methods, covering popular
methods such as the block coordinate gradient descent (BCGD) and the block
coordinate proximal gradient (BCPG), 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 $O(1/r)$, where r
is the iteration index. Moreover, for the case of block coordinate minimization
(BCM) where each block is minimized exactly, we establish the sublinear
convergence rate of $O(1/r)$ without per block strong convexity assumption.
Further, we show that when there are only two blocks of variables, a special
BSUM algorithm with Gauss-Seidel rule can be accelerated to achieve an improved
rate of $O(1/r^2)$.

本文提供了一种对于块坐标下降方法族的统一迭代复杂度分析，涵盖了流行的方法如块坐标梯度下降 (BCGD) 和块坐标近端梯度下降 (BCPG)，更进一步地，对于多块非光滑凸性问题，BSUM 框架覆盖的所有算法均能够实现全局次线性迭代复杂度，而在每个块都被精确最小化的块坐标最小化问题中，本文还在无需每个块强凸性假设下建立了次线性收敛速率。此外，在只有两个变量块的情况下，特殊的 Gauss-Seidel 规则的 BSUM 算法能够加速实现 $O (1/r^2)$ 改善率。