Inexact Coordinate Descent: Complexity and Preconditioning
Rachael Tappenden, Peter Richtárik, Jacek Gondzio · Journal of Optimization Theory and Applications · 2016
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.