Gossip gradient descent

Yang Liu, Ji Liu, Tamer Başar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 (Equation presented) 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 (Equation presented) convergence.

Original languageEnglish (US)
Title of host publication17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1995-1997
Number of pages3
ISBN (Print)9781510868083
StatePublished - Jan 1 2018
Event17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018 - Stockholm, Sweden
Duration: Jul 10 2018Jul 15 2018

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume3
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Other

Other17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
CountrySweden
CityStockholm
Period7/10/187/15/18

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Gossip gradient descent'. Together they form a unique fingerprint.

Cite this