On the Complexity Analysis of Randomized Block-Coordinate Descent
  Methods
  In this paper we analyze the randomized block-coordinate descent (RBCD)
methods proposed in [8,11] for minimizing the sum of a smooth convex function
and a block-separable convex function. In particular, we extend Nesterov's
technique developed in [8] for analyzing the RBCD method for minimizing a
smooth convex function over a block-separable closed convex set to the
aforementioned more general problem and obtain a sharper expected-value type of
convergence rate than the one implied in [11]. Also, we obtain a better
high-probability type of iteration complexity, which improves upon the one in
[11] by at least the amount $O(n/\epsilon)$, where $\epsilon$ is the target
solution accuracy and $n$ is the number of problem blocks. In addition, for
unconstrained smooth convex minimization, we develop a new technique called
{\it randomized estimate sequence} to analyze the accelerated RBCD method
proposed by Nesterov [11] and establish a sharper expected-value type of
convergence rate than the one given in [11].
