Accelerated Gossip via Stochastic Heavy Ball Method

N. Loizou, P. Richtárik
56th Annual Allerton Conference on Communication, Control, and Computing, (2018)

Accelerated Gossip via Stochastic Heavy Ball Method

Keywords

Average Consensus Problem, Linear Systems, Etworks, Randomized Gossip Algorithms, Randomized Kacz-arz, Momentum, Acceleration

Abstract

In this paper we show how the stochastic heavy all method (SHB)—a popular method for solving stochasticonvex and non-convex optimization problems—operates as randomized gossip algorithm. In particular, we focus onwo special cases of SHB: the andomized Kaczmarz methodith momentum and its block variant. Building upon a recentramework for the design and analysis of randomized gossip lgorithms [19] we interpret the distributed nature of theroposed methods. We present novel protocols for solving theverage consensus problem where in each step all nodes of the etwork update their values but only a subset of them exchangeheir private values. Numerical experiments on popular wirelessensor networks showing the benefits of our protocols are also resented.

Code

DOI:

Sources

PDF

See all publications 2018