  In this work we propose a distributed randomized block coordinate descent
method for minimizing a convex function with a huge number of
variables/coordinates. We analyze its complexity under the assumption that the
smooth part of the objective function is partially block separable, and show
that the degree of separability directly influences the complexity. This
extends the results in [Richtarik, Takac: Parallel coordinate descent methods
for big data optimization] to a distributed environment. We first show that
partially block separable functions admit an expected separable
overapproximation (ESO) with respect to a distributed sampling, compute the ESO
parameters, and then specialize complexity results from recent literature that
hold under the generic ESO assumption. We describe several approaches to
distribution and synchronization of the computation across a cluster of
multi-core computers and provide promising computational results.
