Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function

Peter Richtarik*, Martin Takáč

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

428 Scopus citations


In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an e-Accurate solution with probability at least 1-p in at most O((n/e) log (1/p)) iterations, where n is the number of blocks. This extends recent results of Nesterov (SIAM J Optim 22(2): 341-362, 2012), which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing efrom 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 first true iteration complexity bounds. For strongly convex functions the method converges linearly. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale l1-regularized least squares problems with a billion variables.

Original languageEnglish (US)
Pages (from-to)1-38
Number of pages38
JournalMathematical Programming
Issue number1-2
StatePublished - Jan 1 2014


  • Block coordinate descent
  • Composite minimization
  • Convex optimization
  • Coordinate relaxation
  • Gauss-Seidel method
  • Gradient descent
  • Huge-scale optimization
  • Iteration complexity
  • Sparse regression

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function'. Together they form a unique fingerprint.

Cite this