A Differentially Private Method for Distributed Optimization in Directed Networks via State Decomposition

In this article, we study the problem of consensus-based distributed optimization, where a network of agents, abstracted as a directed graph, aims to minimize the sum of all agents' cost functions collaboratively. In the existing distributed optimization approaches (Push-Pull/AB) for directed graphs, all the agents exchange their states with neighbors to achieve the optimal solution with a constant step size, which may lead to the disclosure of sensitive and private information. For privacy preservation, we propose a novel state-decomposition-based gradient tracking approach (SD-Push-Pull) for distributed optimization over directed networks that preserves differential privacy, which is a strong notion that protects agents' privacy against an adversary with arbitrary auxiliary information. The main idea of the proposed approach is to decompose the gradient state of each agent into two substates. Only one substate is exchanged by the agent with its neighbors over time, and the other one is not shared. That is to say, only one substate is visible to an adversary, protecting the sensitive information from being leaked. It is proved that under certain decomposition principles, a bound for the suboptimality of the proposed algorithm can be derived, and the differential privacy is achieved simultaneously. Moreover, the tradeoff between differential privacy and the optimization accuracy is also characterized. Finally, a numerical simulation is provided to illustrate the effectiveness of the proposed approach.