  


Iteration Complexity of Randomized BlockCoordinate Descent Methods for Minimizing a Composite Function
Peter Richtarik (peter.richtariked.ac.uk) Abstract: In this paper we develop a randomized blockcoordinate descent method for minimizing the sum of a smooth and a simple nonsmooth blockseparable convex function and prove that it obtains an $\epsilon$accurate solution with probability at least $1\rho$ in at most $O(\tfrac{n}{\epsilon} \log \tfrac{1}{\rho})$ iterations, where $n$ is the number of blocks. For strongly convex functions the method converges linearly. This extends recent results of Nesterov [Efficiency of coordinate descent methods on hugescale optimization problems, CORE Discussion Paper \#2010/2], which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing $\epsilon$ from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving true iteration complexity bounds. In the smooth case we also allow for arbitrary probability vectors and nonEuclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve hugescale $\ell_1$regularized least squares and support vector machine problems with a billion variables. Keywords: Block coordinate descent, iteration complexity, composite minimization, coordinate relaxation, alternating minimization, convex optimization, L1regularization, large scale support vector machines Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF] Entry Submitted: 07/06/2011 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  