Multi-agent structured optimization over message-passing architectures with bounded communication delays

We consider the problem of solving structured convex optimization problems over a network of agents with communication delays. It is assumed that each agent performs its local updates using possibly outdated information from its neighbors under the assumption that the delay with respect to each neighbor is bounded but otherwise arbitrary. The private objective of each agent is represented by the sum of two possibly nonsmooth functions one of which is composed with a linear mapping. The global optimization problem consists of the aggregate of the local cost functions and a common Lipschitz-differentiable function. In the case when the coupling between agents is represented only through the common function, we employ the primal-dual algorithm proposed by Vü and Condat. In the case when the linear maps introduce additional coupling between agents a new algorithm is developed. In both cases convergence is obtained under a strong convexity assumption. To the best of our knowledge, this is the first time that this form of delay is analyzed for a primal-dual algorithm in a message-passing local-memory model.