Differentially Private Gossip Gradient Descent

In this paper, we study a problem of learning a linear regression model distributively with a network of N interconnected agents in which each agent can deploy an online learning algorithm to adaptively learn the regression model using its private data. The goal of the problem is to devise a distributed algorithm, under the constraint that each agent can communicate only with its neighbors depicted by a connected communication graph, which enables all N agents converge to the true model, with a performance comparable to that of conventional centralized algorithms. We propose a differentially private distributed algorithm, called private gossi» gradient descent, and establish E-differential privacy and Oleft(sqrt{frac{log {2}t}{epsilon(1-lambda-{2})Nt}}right) convergence, where A2 is the second largest eigenvalue of the expected gossip matrix corresponding to the communication graph.