On distributed averaging algorithms and quantization effects

By Angelia Nedić, Alexander Olshevsky, Asuman E. Ozdaglar, John N. Tsitsiklis. 2007

616 citations recorded by the source corpus.

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

1. Angelia Nedić
2. Alexander Olshevsky
3. Ali H. Sayed
4. Ji Liu
5. Aryan Mokhtari
6. Wei Shi
7. Wei Ren
8. Guanrong Chen

Citations in the corpus

• D2: Decentralized Training over Decentralized Data (2018, background): “In contrast, decentralized algorithms can work on any connected network and only rely on the information exchange between neighbor workers [Kashyap et al., 2007, Lavaei and Murray, 2012, Nedic et al., 2009].”
• An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination (2012, background): “It is important to quantify the effects of the asynchronous communication on the consensus problem.”
• Distributed optimization over time-varying directed graphs (2013, neutral): “As for the second statement, when each of the matrices A ( t ) is doubly stochastic, the results of [16] imply that if where ¯ x is the average entry of x ( s ).”
• Gossip consensus algorithms via quantized communication (2009, background): “Related works The constraint of quantization, due to the use of digital channels or to computing and memory constraints, has been considered in consensus problems in several recent papers [17,4,8,9,1,7,13,18].”
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, background): “] if the ≥ − An explicit expression of δ in terms of n can be found in [43 more specific Assumption 3 is made.”
• Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, background): “Similarly, for undirected case, the possibility of modifying the protocol by instead choosing a symmetric matrix A leads to good bounds on δ and λ [27].”
• Distributed subgradient methods and quantization effects (2008, methodology): “This bound is an immediate consequence of Lemma 5 in [13], stating that3 under Assumptions 1 and 2, for all k with V (kB) > 0, V (kB)− V ((k + 1)B) V (kB) ≥ η 2n2 .”
• An Exact Quantized Decentralized Gradient Descent Algorithm (2018, methodology): “Note that the vanilla DGD method converges to a neighborhood of the optimal solution in the presence of quantization noise where the radius of convergence depends on the variance of quantization error [10], [11], [27], [30].”
• A Method to Improve Consensus Averaging using Quantized ADMM (2019, background): “To reduce communication costs, quantized consensus algorithms have been proposed in [7]–[9], [11], [19] where exchanges between nodes are quantized.”
• Discontinuities and hysteresis in quantized average consensus (2010, positive): “A number of publications have discussed –mostly in discrete-time systems– several options to deal with the quantization constraint, namely uniform deterministic quantizers [13, 18], uniform randomized quantizers [2], logarithmic quantizers [5], and adaptive quantizers [17].”
• Distributed Finite-Time Average Consensus in Digraphs in the Presence of Time Delays (2015, background): “It has been shown in [13] that under a fixed interconnection topology, average consensus can be achieved by performing a linear iteration in a distributed fashion as long as the interconnection topology is strongly connected and balanced, while gossip algorithms [14] and convex optimization [15]–…”
• Nested Distributed Gradient Methods with Adaptive Quantized Communication (2019, methodology): “Common approaches include, but are not limited to, allowing the number of quantization levels to approach infinity [20]–[24], preserving the statistical properties of vectors with probabilistic quantization [15], [21], [22], using weighted averages of quantized consensus 2019 IEEE 58th Conference on”
• On the Convergence Time of Asynchronous Distributed Quantized Averaging Algorithms (2010, methodology): “rate of distributed real-valued averaging algorithms on switching graphs in [ 15 ] will be employed”
• A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, background): “The value 1−λn(W) 1−λ2(W) is understood as the condition number4 of the network and aligned with the scalability of the simplest linear iterations for distributed averaging [51].”