Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control

By Alexander Olshevsky. 2014

89 citations recorded by the source corpus.

We describe a protocol for the average consensus problem on any fixed undirected graph whose convergence time scales linearly in the total number nodes $n$. The protocol is completely distributed, with the exception of requiring all nodes to know the same upper bound $U$ on the total number of nodes which is correct within a constant multiplicative factor. We next discuss applications of this protocol to problems in multi-agent control connected to the consensus problem. In particular, we describe protocols for formation maintenance and leader-following with convergence times which also scale linearly with the number of nodes. Finally, we develop a distributed protocol for minimizing an average of (possibly nondifferentiable) convex functions $ (1/n) \sum_{i=1}^n f_i(\theta)$, in the setting where only node $i$ in an undirected, connected graph knows the function $f_i(\theta)$. Under the same assumption about all nodes knowing $U$, and additionally assuming that the subgradients of each $f_i(\theta)$ have absolute values upper bounded by some constant $L$ known to the nodes, we show that after $T$ iterations our protocol has error which is $O(L \sqrt{n/T})$.

Subfields: Computer Networks and Communications

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

Citations in the corpus

Federated learning of predictive models from federated Electronic Health Records (2018, methodology): “[19] The LAC algorithm is an iterative algorithm that takes smalls steps towards the optimal solution at each iteration utilizing a fixed but small step size and is shown to have convergence rate.”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, methodology): “Partial progress was made in [18], [21], where, under the assumption that all nodes know an order-accurate bound on the total number of nodes in the network, it was shown that we can use the linear time convergence of average consensus described in Theorem 6 to obtain a corresponding convergence tim”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “Some examples include distributed averaging [7,50,72], distributed spectrum sensing [1], formation control [49, 58], power system control [21, 55], statistical inference and learning [20, 45, 53].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “For more recent results on randomized gossip algorithms we suggest [217, 106, 148, 109, 131, 6].”
Accelerated Distributed Nesterov Gradient Descent (2017, unknown): “, [32, 4, 22, 15, 8, 30, 19, 20, 17, 26, 38, 16], most of which are distributed gradient descent algorithms based on a consensus scheme [24].”
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks (2018, background): “Particularly, for fixed undirected graphs, in the worst case we have χ(W ) = O(m(2)) [65].”
Harnessing smoothness to accelerate distributed optimization (2016, background): “Extensions of these work have been proposed that deal with various realistic conditions, such as stochastic subgradient errors [9], directed or random communication graph [10]–[12], linear scaling in network size [13], heterogeneous local constraints [14], [15].”
A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, methodology): “By using Nesterov’s acceleration technique, reference [28] shows that the scaling factor of a new average consensus protocol can be improved to O ( n ); When the nonsmooth terms r i ’s are absent, reference [35] shows that the scaling factor of a new dual based accelerated distributed gradient…”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, background): “For more recent results on randomized gossip algorithms we suggest [94, 40, 63, 43, 55, 3].”
Distributed Multitask Reinforcement Learning with Quadratic Convergence (2018, methodology): “On the distributed side, we evaluated our algorithm against five other approaches being: 1) ADD [27], 2) ADMM [11], 3) distributed averaging [30], 4) network-newton [26, 25], and 5) sub-gradients.”