On the Complexity Analysis of Randomized Block-Coordinate Descent Methods

Zhaosong Lu and Lin Xiao

May 2013

In this paper we analyze the randomized block-coordinate descent (RBCD) methods for minimizing the sum of a smooth convex function and a block-separable convex function. In particular, we extend Nesterov's technique (SIOPT 2012) 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 in Richtarik and Takac (Math Programming 2012). Also, we obtain a better high-probability type of iteration complexity, which improves upon the one by Richtarik and Takac by at least the amount *O(n/ε)*, where *ε* 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 randomized estimate sequence to analyze the accelerated RBCD method proposed by Nesterov (SIOPT 2012) and establish a sharper expected-value type of convergence rate.

Publication type | TechReport |

Number | MSR-TR-2013-53 |

- New Convex Programs and Distributed Algorithms for Fisher Markets with Linear and Spending Constraint Utilities
- Symmetry Analysis of Reversible Markov Chains
- The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem

> Publications > On the Complexity Analysis of Randomized Block-Coordinate Descent Methods