Optimization Online


On the Complexity Analysis of Randomized Block-Coordinate Descent Methods

Zhaosong Lu(zhaosong***at***sfu.ca)
Lin Xiao(lin.xiao***at***microsoft.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/2013
Entry Accepted: 05/20/2013
Entry Last Modified: 05/20/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society