State of the art. Coordinate (proximal) gradient descent methods [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, see also the recent survey [12]}, gained attention in optimization in the last years due to their fast convergence and small computational cost per iteration. The main differences in all variants of coordinate descent algorithms consist in the way we define the local approximation
function over which we optimize and the criterion of choosing at each iteration the coordinate over which we minimize this local approximation. For updating one (block) variable, while keeping the other variables fixed, two basic choices for the local approximation are usually considered: (i) exact approximation function, leading to coordinate minimization methods [13]}, [14]} and (ii) quadratic approximation function, leading to coordinate gradient descent methods [5]}, [11]}, [12]}. Furthermore, three criteria for choosing the coordinate search used often in these algorithms are the greedy, the cyclic and the random coordinate search, respectively. For cyclic coordinate search convergence rates have been given recently in [13]}, [1]}. Convergence rates for coordinate descent methods based on the Gauss-Southwell rule were derived in [11]}. Another interesting approach is based on random coordinate descent, where the coordinate search is random. Complexity results on random coordinate descent methods were obtained in [5]} for smooth convex functions. The extension to composite objective functions were given in [3]}, [9]}, [6]}, [10]}. However, all these papers studied optimization models where the second term, usually assumed nonsmooth, is separable, i.e., \(\psi (x) =\sum _{i=1}^n \psi _i(x_i)\) , with \(x_i\)  is the \(i\) th component of \(x\) .
