Parallel and distributed random coordinate descent method for convex error bound minimization

In this paper we propose a parallel and distributed random (block) coordinate descent method for minimizing the sum of a partially separable smooth convex function and a fully separable non-smooth convex function. In this algorithm the iterate updates are done independently and thus it is suitable for parallel and distributed computing architectures. We prove linear convergence rate for the proposed algorithm on the class of problems satisfying a generalized error bound property. We also show that the theoretical estimates on the convergence rate depend on the number of blocks chosen randomly and a natural measure of separability of the objective function. Numerical simulations are also provided to confirm our theory.