A new perspective on randomized gossip algorithms

By Nicolas Loizou, Peter Richtárik. 2016

32 citations recorded by the source corpus.

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 that 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 gossip 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.

Subfields: Computer Networks and Communications, Public Health, Environmental and Occupational Health, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Peter Richtárik
2. Sebastian U. Stich
3. Nicolas Loizou
4. Martin Jaggi
5. Anastasia Koloskova
6. Martin Takác
7. Sadra Boreiri
8. Ahmed Khaled

In Public Health, Environmental and Occupational Health

1. Nicolas Loizou
2. Peter Richtárik
3. Martin Takác
4. Sebastian U. Stich
5. Martin Jaggi
6. Anastasia Koloskova
7. Sadra Boreiri

In Statistical and Nonlinear Physics

1. Nicolas Loizou
2. Peter Richtárik
3. Martin Takác
4. Sebastian U. Stich
5. Martin Jaggi
6. Anastasia Koloskova

Citations in the corpus

• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “In this case p = ρ ( G ) / | E | , where ρ ( G ) denotes the algebraic connectivity of the network (Fiedler, 1973; Boyd et al., 2006; Loizou & Richt´arik, 2016).”
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “ar systems with real matrices. In the second experiment we computationally verify Theorem 8 (comparison between the mSGD and smSGD methods). In the last experiment building upon the recent results of [38] we show how the addition of the momentum accelerates the pairwise randomized gossip (PRG) algor”
• Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “sis beyond quadratics was performed in [67, 47, 58], a parallel method was developed in [59], duality was explored in [68] and acceleration in [15]. 2.4. Randomized gossip algorithms. It was shown in [20, 34] that for a suitable matrix A encoding the structure of a graph, and for b= 0, the applicati”
• Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “ to the more general case of minimization of convex and non-convex functions in the stochastic setting. Finally, sketch-and-project algorithms have been used for solving the average consensus problem [27,20] popular in distributed optimization literature. Our results could also be useful in this are”
• Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “In [46], building upon the results from [26], a connection between the area of randomized iterative methods for linear systems and gossip algorithms was established and block gossip algorithm were developed.”
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In the special case that only one edge is selected in each iteration (Sk ∈ Rm×1) the update rule of mRBK is simplified to the update rule of mRK.”