Projects per year
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.
Original language  English 

Pages (fromto)  138 
Number of pages  38 
Journal  Mathematical programming 
Volume  144 
Issue number  12 
DOIs  
Publication status  Published  Apr 2014 
Keywords
 Block coordinate descent
 Hugescale optimization
 Composite minimization
 Iteration complexity
 Convex optimization
 LASSO
 Sparse regression
 Gradient descent
 Coordinate relaxation
 Gauss–Seidel method
Fingerprint
Dive into the research topics of 'Iteration complexity of randomized blockcoordinate descent methods for minimizing a composite function'. Together they form a unique fingerprint.Projects
 1 Finished

Science and Innovation: Numerical Algorithms and Intelligent Software for the Evolving HPC Platform
1/08/09 → 31/07/14
Project: Research