Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation Over Adaptive Networks

By Sheng-Yuan Tu, Ali H. Sayed. IEEE Transactions on Signal Processing, 2012

469 citations recorded by the source corpus.

Adaptive networks consist of a collection of nodes with adaptation and learning abilities. The nodes interact with each other on a local level and diffuse information across the network to solve estimation and inference tasks in a distributed manner. In this work, we compare the mean-square performance of two main strategies for distributed estimation over networks: consensus strategies and diffusion strategies. The analysis in the paper confirms that under constant step-sizes, diffusion strategies allow information to diffuse more thoroughly through the network and this property has a favorable effect on the evolution of the network: diffusion networks are shown to converge faster and reach lower mean-square deviation than consensus networks, and their mean-square stability is insensitive to the choice of the combination weights. In contrast, and surprisingly, it is shown that consensus networks can become unstable even if all the individual nodes are stable and able to solve the estimation task on their own. When this occurs, cooperation over the network leads to a catastrophic failure of the estimation task. This phenomenon does not occur for diffusion networks: we show that stability of the individual nodes always ensures stability of the diffusion network irrespective of the combination topology. Simulation results support the theoretical findings.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/f7355f8688d52f515b5442f3ff76e6a1ceb82f15

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

Citations in the corpus

Distributed Policy Evaluation Under Multiple Behavior Strategies (2013, background): “It has been shown in [22] that the dynamics of diffusion networks leads to enhanced stability and lower mean-square-error (MSE) than consensus networks.”
Adaptive Networks (2014, methodology): “This is because the asymmetry can cause an unstable growth in the state of the network [99].”
Multitask Diffusion Adaptation Over Networks (2013, background): “In addition, for data processing over adaptive networks, diffusion strategies have been shown to have superior stability and performance ranges [19] than consensus-based implementations.”
Adaptation, Learning, and Optimization over Networks (2014, background): “237) is smaller or equal to one [249]: |λk(A)|(2) ( 1 − |λk(A) − μλm(H)|(2) ) 1 − |λk(A)|2 (1 − μλm(H))2 ≤ 1 (11.”
Excess-Risk of Distributed Stochastic Learners (2013, background): “These coefficients are chosen to satisfy: N∑ `=1 a`k=1, a`k = 0 if nodes (`,k) are not connected (12) We emphasize that we are only requiring A to be leftstochastic, meaning that only each of its columns should add up to one rather than each of its columns and rows.”
Diffusion Adaptation over Networks (2012, background): “For further details and other results on the meansquare performance of diffusion networks in relation to consensus networks, the reader is referred to [89,90].”
Robust Distributed Diffusion Recursive Least Squares Algorithms With Side Information for Adaptive Networks (2018, background): “According to the cooperation strategies between interconnected nodes, existing algorithms can be categorized as incremental [9], consensus [10], and diffusion [11]–[14] types.”
Robust Distributed Estimation by Networked Agents (2017, methodology): “The focus of this work is on adaptive diffusion strategies based on the least-mean-squares (LMS) algorithm, among which the adapt-then-combine (ATC) strategy is of particular interest [8]– [12], since it has been shown to outperform other distributed strategies including consensus-type implementatio”
Distributed Algorithms for Aggregative Games on Graphs (2016, background): “Notably, extensions of consensus based algorithms have also been studied in the domain of distributed regression [48], estimation and inference tasks [58, 59].”
Distributed multi-task classification: a decentralized online learning approach (2017, methodology): “Since the previous research (Tu and Sayed 2012) shows that diffusion learning outperforms incremen- 2 Although dynamic relationship seems more meaningful in many scenarios, we can’t confirm B is p.s.d and hence this methods leads to the challenge of theoretical analysis (Saha et al. 2011).”