- On the Complexity Analysis of Randomized Block-Coordinate Descent Methods Zhaosong Lu(zhaosongsfu.ca) Lin Xiao(lin.xiaomicrosoft.com) Abstract: 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 implied 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/\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 randomized estimate sequence to analyze the accelerated RBCD method proposed by Nesterov (SIOPT 2012) and establish a sharper expected-value type of convergence rate. Keywords: randomized coordinate descent, accelerated coordinate descent, iteration complexity, convergence rate, composite minimization Category 1: Convex and Nonsmooth Optimization Citation: Microsoft Research Technical Report, MSR-TR-2013-53, May 2013. Download: [PDF]Entry Submitted: 05/20/2013Entry Accepted: 05/20/2013Entry Last Modified: 05/20/2013Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.