  The iteration complexity of the block-coordinate descent (BCD) type algorithm
has been under extensive investigation. It was recently shown that for convex
problems the classical cyclic BCGD (block coordinate gradient descent) achieves
an $\mathcal{O}(1/r)$ complexity ($r$ is the number of passes of all blocks).
However, such bounds are at least linearly depend on $K$ (the number of
variable blocks), and are at least $K$ times worse than those of the gradient
descent (GD) and proximal gradient (PG) methods. In this paper, we aim to close
such theoretical performance gap between cyclic BCD and GD/PG. First we show
that for a family of quadratic nonsmooth problems, the complexity bounds for
cyclic Block Coordinate Proximal Gradient (BCPG), a popular variant of BCD, can
match those of the GD/PG in terms of dependency on $K$ (up to a $\log^2(K)$
factor). For the same family of problems, we also improve the bounds of the
classical BCD (with exact block minimization) by an order of $K$. Second, we
establish an improved complexity bound of Coordinate Gradient Descent (CGD) for
general convex problems which can match that of GD in certain scenarios. Our
bounds are sharper than the known bounds as they are always at least $K$ times
worse than GD. Our analyses do not depend on the update order of block
variables inside each cycle, thus our results also apply to BCD methods with
random permutation (random sampling without replacement, another popular
variant).
