  In this paper, a class of large-scale distributed nonsmooth convex
optimization problem over time-varying multi-agent network is investigated.
Specifically, the decision space which can be split into several blocks of
convex set is considered. We present a distributed block coordinate descent
(DSBCD) method in which for each node, information communication with other
agents and a block Bregman projection are performed in each iteration. In
contrast to existing work, we do not require the projection is operated on the
whole decision space. Instead, in each step, distributed projection procedure
is performed on only one random block. The explicit formulation of the
convergence level depending on random projection probabilities and network
parameters is achieved. An expected $O(1/\sqrt{T})$ rate is achieved. In
addition, we obtain an explicit $\mathcal{O}(b^2/\epsilon^2)$ complexity bound
with target accuracy $\epsilon$ and characteristic constant factor $b$. The
complexity with dependency on $\epsilon$ and $b$ is shown to be the best known
in this literature.

Optimization and Control