Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

In this paper we develop a randomized block-coordinate descent method for\nminimizing the sum of a smooth and a simple nonsmooth block-separable convex\nfunction and prove that it obtains an $\\epsilon$-accurate solution with\nprobability at least $1-\\rho$ in at most $O(\\tfrac{n}{\\epsilon} \\log\n\\tfrac{1}{\\rho})$ iterations, where $n$ is the number of blocks. For strongly\nconvex functions the method converges linearly. This extends recent results of\nNesterov [Efficiency of coordinate descent methods on huge-scale optimization\nproblems, CORE Discussion Paper #2010/2], which cover the smooth case, to\ncomposite minimization, while at the same time improving the complexity by the\nfactor of 4 and removing $\\epsilon$ from the logarithmic term. More\nimportantly, in contrast with the aforementioned work in which the author\nachieves the results by applying the method to a regularized version of the\nobjective function with an unknown scaling factor, we show that this is not\nnecessary, thus achieving true iteration complexity bounds. In the smooth case\nwe also allow for arbitrary probability vectors and non-Euclidean norms.\nFinally, we demonstrate numerically that the algorithm is able to solve\nhuge-scale $\\ell_1$-regularized least squares and support vector machine\nproblems with a billion variables.\n