Inexact Coordinate Descent: Complexity and Preconditioning

Rachael Tappenden*, Peter Richtarik, Jacek Gondzio

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

One of the key steps at each iteration of a randomized block coordinate descent method consists in determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. In this work, we relax this requirement and allow for the subproblem to be solved inexactly, leading to an inexact block coordinate descent method. Our approach incorporates the best known results for exact updates as a special case. Moreover, these theoretical guarantees are complemented by practical considerations: the use of iterative techniques to determine the update and the use of preconditioning for further acceleration.

Original languageEnglish (US)
Pages (from-to)144-176
Number of pages33
JournalJournal of Optimization Theory and Applications
Volume170
Issue number1
DOIs
StatePublished - Jul 1 2016

Keywords

  • Block coordinate descent
  • Conjugate gradients
  • Convex optimization
  • Inexact methods
  • Iteration complexity
  • Preconditioning

ASJC Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Inexact Coordinate Descent: Complexity and Preconditioning'. Together they form a unique fingerprint.

Cite this