Gossip Gradient Descent

We consider a problem of learning a linear regression model distributively with a network of N interconnected agents which receive private streaming data. Each agent can deploy an online learning algorithm, e. g. stochastic gradient descent, to learn adaptively the regression model using its receiving private data. The goal is to devise an algorithm for each agent, under the constraint that each of them can communicate only with its neighboring agents based on a communication graph, to enable each agent converge to the true model with a performance comparable to that of the traditional centralized solution. We propose an algorithm called gossip gradient descent, and establish O q log t (1−λ2)N t convergence in expectation and mean square, where λ2 is the second largest eigenvalue of the expected gossip matrix corresponding to the underlying communication graph. For the case when agents are privacy sensitive, we propose a differentially private variant of the algorithm, which achieves ϵ-differential privacy and O r log2 t ϵ(1−λ2)N t! convergence.

Authors

• Yang Liu College of Computer Science, Sichuan University Engineering Research Center of Machine Learning and Industry Intelligence, Ministry of Education
• Ji Liu Advanced Micro Devices, Inc.
• Tamer Basar

Keywords

No keywords are indexed for this paper.