Distributed Composite Optimization with Distributed Composite Block Mirror Descent

This paper investigates a class of large-scale distributed nonsmooth composite optimization problems over time-varying multi-agent networks. Specifically, the decision space, which can be split into several blocks of convex set, is considered. Each node, endowed with a private nonsmooth cost function and a regularization function, aims to minimize the sum of all local functions across the network. We propose a novel distributed composite block mirror descent (DCBMD) method, where each node performs information communication with other agents and executes a block regularized mirror descent in each iteration. In contrast to existing work on distributed composite optimization, for the decision space with block structure, we do not require the projection to be operated on the whole decision space. Instead, in each step, a distributed projection procedure induced by a composite mirror descent scheme is performed on only one randomly selected block, significantly saving the iteration cost. The explicit formulation of the convergence bound depending on random projection probabilities and network parameters is achieved. An optimal convergence rate O(1/√T) is rigorously derived. The DCBMD provides a generic framework for different projection-based distributed algorithms. © 1963-2012 IEEE.