Randomized gossip algorithms

By Stephen P. Boyd, Arpita Ghosh, Balaji Prabhakar, Devavrat Shah. 2006

2,623 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Algorithms & Complexity

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

In Algorithms & Complexity

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “See for instance the discussion on clock models in [78].”
Privacy Amplification by Decentralization (2020, positive): “We would also like to study randomized gossip algorithms [8]: these protocols are popular for decentralized optimization in machine learning (see [12] and references therein) and were recently shown to provide differential privacy guarantees in the specific context of rumor spreading [5].”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “…averaging with a randomly sampled mixing matrix W ∼ W it holds for a value p ≥ 0 (related to the spectrum of E W (cid:62) W ), that is, the averaging step brings the values in the columns of X ∈ R d × n closer to their row-wise average ¯ X := X · 1 n 11 in expectation (see e.g. Boyd et al., 2006).”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, background): “We here in particular focus on approached based on gossip averaging (Kempe et al., 2003; Xiao and Boyd, 2004; Boyd et al., 2006) whose convergence rate typically depends on the spectral gap ρ ≥ 0 of the mixing matrix (Xiao and Boyd, 2004).”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, methodology): “The decentralized training has been proven to be superior to the centralized training in terms of reducing the communication cost [Boyd et al., 2006], especially when the model is huge and the network bandwidth and latency are less satisfactory.”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “or constraining the number of allowable links, have been proposed [17].”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “Gossip-type algorithms converge linearly for average consensus (Kempe et al., 2003; Xiao & Boyd, 2004; OlfatiSaber & Murray, 2004; Boyd et al., 2006).”
Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, background): “Following the standard practice in the fully decentralized literature (Boyd et al., 2006), each user regularly becomes active at the ticks of an independent local clock which follows a Poisson distribution.”
Distributed Learning over Unreliable Networks (2018, background): “There are many works (Boyd et al., 2006; Li & Zhang, 2010; Lobel & Ozdaglar, 2011; Nedic et al., 2017; Nedić & Olshevsky, 2015) studying the random topology decentralized SGD algorithms under different assumptions.”
Personalized and Private Peer-to-Peer Machine Learning (2017, methodology): “Specifically, we operate in the asynchronous time model (Boyd et al., 2006): each agent has a local clock ticking at the times of a rate 1 Poisson process, and wakes up when it ticks.”
Decentralized Collaborative Learning of Personalized Models over Networks (2016, methodology): “Several peer-to-peer algorithms have been developed for decentralized averaging (Kempe et al., 2003; Boyd et al., 2006; Colin et al., 2015) and optimization (Nedic and Ozdaglar, 2009; Ram et al., 2010; Duchi et al., 2012; Wei and Ozdaglar, 2012, 2013; Iutzeler et al., 2013; Colin et al., 2016).”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, neutral): “We assume for simplicity that each node has a clock ticking at a Poisson rate equals to 1 , so it is equivalent to a global clock ticking at a Poisson rate of n , and then drawing an edge uniformly at random (see (Boyd et al., 2006) for more details).”
An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination (2012, background): “…generalized coordinates, Mi(qi) ∈ Rp×p is the symmetric positive-definite inertia matrix, Ci(qi, q̇i)q̇i ∈ Rp is the vector of Coriolis and centrifugal torques,gi(qi) is the vector of gravitational torques, andτi ∈ Rp is the vector of torques produced by the actuators associated with theith agent.”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, positive): “Gossip algorithms are procedures for achieving consensus in a network robustly by randomly selecting one edge in the network for communication at each iteration; upon selection, nodes and average their values [25].”
Communication Compression for Decentralized Training (2018, methodology): “Boyd et al. [2006] uses a randomized weighted matrix and studied the effectiveness of the weighted matrix in different situations. Two methods [Li et al., 2017, Shi et al., 2015] were proposed to reduce the steady point error in decentralized gradient descent convex optimization. Dobbe et al. [2017]”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, methodology): “Decentralized algorithms tackle this problem by replacing targeted communication by local averaging of the values of neighboring nodes [9].”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, background): “…some ε > 0 , for which it is known that the random graph is connected with high probability [17]. having neighboring nodes exchange their degrees—determining the optimal matrices A k involves solving a separate network-wide optimization problem; see [23] for a distributed approximation algorithm.”
Distributed Robust Learning (2014, methodology): “Distributed learning methods can be roughly divided into two categories: the decentralized gossip-type algorithms [2] and the algorithms constructed on the map-reduce framework [7].”
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, methodology): “Indeed, (a) for a single machine the optimal number of gradient steps to optimize a function is proportional to the square root of the condition number (Nesterov, 2004), and (b) for mean estimation, the optimal number of communication steps is proportional to the diameter of the network in centraliz”