Dual Consensus Proximal Algorithm for Multi-Agent Sharing Problems

This work considers multi-agent sharing optimization problems, where each agent owns a local smooth function plus a non-smooth function, and the network seeks to minimize the sum of all local functions plus a coupling composite function (possibly non-smooth). For this non-smooth setting, centralized algorithms are known to converge linearly under certain conditions. On the other hand, decentralized algorithms have not been shown to achieve linear convergence under the same conditions. In this work, we propose a decentralized proximal primal-dual algorithm and establish its linear convergence under weaker conditions than existing decentralized works. Our result shows that decentralized algorithms match the linear rate of centralized algorithms without any extra condition. Finally, we provide numerical simulations that illustrate the theoretical findings and show the advantages of the proposed method.