  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)$.
