R. Tappenden, P. Richtarik and J. Gondzio
Abstract
In this paper we consider the problem of minimizing a convex function
using a randomized block coordinate descent method. One of the key
steps at each iteration of the algorithm is 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 his 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 as well as the use of preconditioning
for further acceleration.
Key words: inexact methods, block coordinate descent, convex optimization, iteration complexity, preconditioning, conjugate gradients.