Fast linear iterations for distributed averaging

By Lin Xiao, Stephen P. Boyd. 2003

3,003 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics, 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 Statistical and Nonlinear Physics

In Algorithms & Complexity

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “Commonly used weights are for instance the MetropolisHastings weights wij = wji = min { 1 deg(i)+1 , 1 deg(j)+1 } for (i, j) ∈ E, see also (Xiao & Boyd, 2004; Boyd et al., 2006) for further guidelines.”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “This will not only guarantee ρ > 0 but these weights can easily be computed in a local fashion on each node (Xiao and Boyd, 2004).”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, methodology): “A common practice is to use an equal weight mixing matrix as [5, 10, 29]: where j L j denotes the graph Laplacian at the k -th iteration.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “For a ﬁxed gossip matrix W , the classical algorithm analyzed in (Xiao & Boyd, 2004) corresponds to the choice in (3), with (E-G) standing for exact gossip .”
An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination (2012, methodology): “Other than the smallest nonzero eigenvalue of the Laplacian m trix, another commonly used measure for the convergence speed is the following ratio, introduce d in [156], [157]:”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, background): “(ii) Laplacian-based constant edge weight matrix [28,33], where L is the Laplacian matrix of the graph G and τ > λ max ( L ) is a scaling parameter.”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, background): “(2), where A k is optimized for the particular graph topology [22], [23].”
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, background): “However, in the presence of large degree nodes, weighted Laplacian matrices are usually a better choice, and the problem of optimizing these weights is known as the fastest distributed consensus averaging problem and is investigated by [20, 21].”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “The mixing matrix W is chosen as the fastest (asymmetric) linear consensus matrix [71].”
Minimizing Effective Resistance of a Graph (2008, background): “Other convex problems involving edge weights on graphs include the problem of finding the fastest mixing Markov chain on a given graph [BDX04], [GHW05], [SBXD], the problem of finding the edge weights (which can be negative) that give the fastest convergence in an averaging network [XB04], and the p”
Diffusion Least-Mean Squares Over Adaptive Networks: Formulation and Performance Analysis (2008, background): “Possible choices for the combiner are the Metropolis, the Laplacian and the nearest neighbor rules [20]–[22].”
Finite-Time Consensus Problems for Networks of Dynamic Agents (2007, background): “In [4], Xiao and Boyd considered and solved the problem of weight design by using semi-deﬁnite convex programming, and the convergence rate is also increased.”
Adaptation, Learning, and Optimization over Networks (2014, background): “, [18, 26, 32, 46, 84, 87, 128, 138, 139, 175, 176, 186, 199, 205, 209, 215, 225, 242, 243, 266, 268]; (c) diffusion strategies — see, e.”
Diffusion Least-Mean Squares With Adaptive Combiners: Formulation and Performance Analysis (2010, background): “Table I shows examples of static combination rules, which keep constant; see, e.g., [15] and [17]–[22].”
Consensus problems in networks of agents with switching topology and time-delays (2004, methodology): “We refer the reader to [34] for a network design problem for reaching average-consensus using a semideﬁnite programming approach.”
Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems (2013, background): “…to a ﬁxed-point that is the projection of the x 0 into the 1 -eigenspace of T , i.e. x ⋆ lim k →∞ Proposition 1: The iterations (2) converge to a ﬁxed-point in Im ( V ) if and only if Proof: The result is an extension of [20, Theorem 1] for the case of 1 -eigenspace of T with dimension m > 1 .”
Decentralized Robust Adaptive Control for the Multiagent System Consensus Problem Using Neural Networks (2009, background): “This is because, on the one hand, research on the fixed topology is the foundation of various kinds of switching topologies; on the other hand, the fixed topology is suitable for many applications in distributed computation, formation control, and data fusion of sensor networks [27]–[29].”
Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, methodology): “5 Additional experiments were conducted selecting the matrix A as solution of the fastest distributed linear averaging problem deﬁned in [62] (Appendix H.4).”
Distributed Matrix Scaling and Application to Average Consensus in Directed Graphs (2013, background): “…(or agreement) problem is a special case of distributed function calculation where each node in the network possesses an initial value and the nodes need to agree on the same value, typically by calculating (via some iterative algorithm) the same function of their initial values [1], [8], [9].”