Sorry, you need to enable JavaScript to visit this website.

A New Perspective on Randomized Gossip Algorithms

Citation Author(s):
Nicolas Loizou, Peter Richtarik
Submitted by:
Nicolas Loizou
Last updated:
5 December 2016 - 8:10am
Document Type:
Poster
Document Year:
2016
Event:
Presenters Name:
Nicolas Loizou
Paper Code:
GlobalSIP1600

Abstract 

Abstract: 

In this short note we propose a new approach for the design and analysis of randomized gossip algorithms which can be used to solve the average consensus problem. We show how the Randomized Block Kaczmarz (RBK) method—a method for solving linear systems—works as gossip algorithm when applied to a special system encoding the underlying network. The famous pairwise gossip algorithm arises as a special case. Subsequently, we reveal a hidden duality of randomized gos- sip algorithms, with the dual iterative process maintaining a set of numbers attached to the edges as opposed to nodes of the network. We prove that RBK obtains a superlinear speedup in the size of the block, and demonstrate this effect through experiments.

up
0 users have voted:

Dataset Files

PosterGlobalSip.pdf

(844)