Estimation Network Design framework for efficient distributed optimization

Abstract

Distributed decision problems feature a group of agents that can only communicate over a peer-to-peer network, without a central memory. In applications such as network control and data ranking, each agent is only affected by a small portion of the decision vector: this sparsity is typically ignored in distributed algorithms, while it could be leveraged to improve efficiency and scalability. To address this issue, our recent paper [1] introduces Estimation Network Design (END), a graph theoretical language for analysis and design of distributed iterations. END methods can be tuned to exploit the sparsity of specific problem instances, reducing communication overhead and minimizing redundancy, yet without requiring case-by-case convergence analysis. In this paper, we showcase the flexibility of END in the context of distributed optimization. In particular, we study the sparsity-aware version of many established algorithms, including ADMM, AugDGM and PushSum DGD. Simulations on an estimation problem in sensor networks demonstrate that END algorithms can boost convergence speed and greatly reduce the communication cost.