Provably Accelerated Randomized Gossip Algorithms

Nicolas Loizou; Michael Rabbat; Peter Richtarik

doi:10.1109/ICASSP.2019.8683847

Provably Accelerated Randomized Gossip Algorithms

Nicolas Loizou, Michael Rabbat, Peter Richtarik

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

10 Scopus citations

Abstract

In this work we present novel provably accelerated gossip algorithms for solving the average consensus problem. The proposed protocols are inspired from the recently developed accelerated variants of the randomized Kaczmarz method - a popular method for solving linear systems. In each gossip iteration all nodes of the network update their values but only a pair of them exchange their private information. Numerical experiments on popular wireless sensor networks showing the benefits of our protocols are also presented.

Original language	English (US)
Title of host publication	ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	7505-7509
Number of pages	5
ISBN (Print)	9781479981311
DOIs	https://doi.org/10.1109/ICASSP.2019.8683847
State	Published - Apr 17 2019

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

Access to Document

10.1109/ICASSP.2019.8683847

https://repository.kaust.edu.sa/bitstream/10754/653117/5/AccGossip.pdf

Cite this

@inproceedings{71f01083c4034bf48ba7cb4bf262853e,

title = "Provably Accelerated Randomized Gossip Algorithms",

abstract = "In this work we present novel provably accelerated gossip algorithms for solving the average consensus problem. The proposed protocols are inspired from the recently developed accelerated variants of the randomized Kaczmarz method - a popular method for solving linear systems. In each gossip iteration all nodes of the network update their values but only a pair of them exchange their private information. Numerical experiments on popular wireless sensor networks showing the benefits of our protocols are also presented.",

author = "Nicolas Loizou and Michael Rabbat and Peter Richtarik",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2019",

month = apr,

day = "17",

doi = "10.1109/ICASSP.2019.8683847",

language = "English (US)",

isbn = "9781479981311",

pages = "7505--7509",

booktitle = "ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

}

Provably Accelerated Randomized Gossip Algorithms. / Loizou, Nicolas; Rabbat, Michael; Richtarik, Peter.
ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Institute of Electrical and Electronics Engineers Inc., 2019. p. 7505-7509.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Provably Accelerated Randomized Gossip Algorithms

AU - Loizou, Nicolas

AU - Rabbat, Michael

AU - Richtarik, Peter

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2019/4/17

Y1 - 2019/4/17

N2 - In this work we present novel provably accelerated gossip algorithms for solving the average consensus problem. The proposed protocols are inspired from the recently developed accelerated variants of the randomized Kaczmarz method - a popular method for solving linear systems. In each gossip iteration all nodes of the network update their values but only a pair of them exchange their private information. Numerical experiments on popular wireless sensor networks showing the benefits of our protocols are also presented.

AB - In this work we present novel provably accelerated gossip algorithms for solving the average consensus problem. The proposed protocols are inspired from the recently developed accelerated variants of the randomized Kaczmarz method - a popular method for solving linear systems. In each gossip iteration all nodes of the network update their values but only a pair of them exchange their private information. Numerical experiments on popular wireless sensor networks showing the benefits of our protocols are also presented.

UR - http://hdl.handle.net/10754/653117

UR - https://ieeexplore.ieee.org/document/8683847/

UR - http://www.scopus.com/inward/record.url?scp=85069468216&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2019.8683847

DO - 10.1109/ICASSP.2019.8683847

M3 - Conference contribution

SN - 9781479981311

SP - 7505

EP - 7509

BT - ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Provably Accelerated Randomized Gossip Algorithms

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this