Communication-efficient distributed online prediction by dynamic model synchronization

Michael Kamp, Mario Boley, Daniel Keren, Assaf Schuster, Izchak Sharfman

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

11 Citations (Scopus)

Abstract

We present the first protocol for distributed online prediction that aims to minimize online prediction loss and network communication at the same time. This protocol can be applied wherever a prediction-based service must be provided timely for each data point of a multitude of high frequency data streams, each of which is observed at a local node of some distributed system. Exemplary applications include social content recommendation and algorithmic trading. The challenge is to balance the joint predictive performance of the nodes by exchanging information between them, while not letting communication overhead deteriorate the responsiveness of the service. Technically, the proposed protocol is based on controlling the variance of the local models in a decentralized way. This approach retains the asymptotic optimal regret of previous algorithms. At the same time, it allows to substantially reduce network communication, and, in contrast to previous approaches, it remains applicable when the data is non-stationary and shows rapid concept drift. We demonstrate empirically that the protocol is able to hold up a high predictive performance using only a fraction of the communication required by benchmark methods.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationEuropean Conference, ECML PKDD 2014 Nancy, France, September 15-19, 2014 Proceedings, Part I
EditorsToon Calders, Floriana Esposito, Eyke Hüllermeier, Rosa Meo
Place of PublicationBerlin Germany
PublisherSpringer
Pages623-639
Number of pages17
ISBN (Electronic)9783662448489
ISBN (Print)9783662448472
DOIs
Publication statusPublished - 2014
Externally publishedYes
EventEuropean Conference on Machine Learning European Conference on Principles and Practice of Knowledge Discovery in Databases 2014 - Nancy, France
Duration: 15 Sep 201419 Sep 2014
https://web.archive.org/web/20140903072633/http://www.ecmlpkdd2014.org/
https://link.springer.com/book/10.1007/978-3-662-44848-9 (Proceedings)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8724
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Conference on Machine Learning European Conference on Principles and Practice of Knowledge Discovery in Databases 2014
Abbreviated titleECML PKDD 2014
CountryFrance
CityNancy
Period15/09/1419/09/14
Internet address

Cite this