  


On the Complexity Analysis of Randomized BlockCoordinate Descent Methods
Zhaosong Lu(zhaosongsfu.ca) Abstract: In this paper we analyze the randomized blockcoordinate descent (RBCD) methods for minimizing the sum of a smooth convex function and a blockseparable convex function. In particular, we extend Nesterov's technique (SIOPT 2012) for analyzing the RBCD method for minimizing a smooth convex function over a blockseparable closed convex set to the aforementioned more general problem and obtain a sharper expectedvalue type of convergence rate than the one implied in Richtarik and Takac (Math Programming 2012). Also, we obtain a better highprobability 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 expectedvalue 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, MSRTR201353, May 2013. Download: [PDF] Entry Submitted: 05/20/2013 Modify/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  