Diffusion Adaptation over Networks

By Ali H. Sayed. arXiv.org, 2012

475 citations recorded by the source corpus.

Adaptive networks are well-suited to perform decentralized information processing and optimization tasks and to model various types of self-organized and complex behavior encountered in nature. Adaptive networks consist of a collection of agents with processing and learning abilities. The agents are linked together through a connection topology, and they cooperate with each other through local interactions to solve distributed optimization, estimation, and inference problems in real-time. The continuous diffusion of information across the network enables agents to adapt their performance in relation to streaming data and network conditions; it also results in improved adaptation and learning performance relative to non-cooperative agents. This article provides an overview of diffusion strategies for adaptation and learning over networks. The article is divided into several sections: 1. Motivation; 2. Mean-Square-Error Estimation; 3. Distributed Optimization via Diffusion Strategies; 4. Adaptive Diffusion Strategies; 5. Performance of Steepest-Descent Diffusion Strategies; 6. Performance of Adaptive Diffusion Strategies; 7. Comparing the Performance of Cooperative Strategies; 8. Selecting the Combination Weights; 9. Diffusion with Noisy Information Exchanges; 10. Extensions and Further Considerations; Appendix A: Properties of Kronecker Products; Appendix B: Graph Laplacian and Network Connectivity; Appendix C: Stochastic Matrices; Appendix D: Block Maximum Norm; Appendix E: Comparison with Consensus Strategies; References.

Subfields: Computational Mechanics, Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/513af7b62378f20a61c14a733b37acc562a78561

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Push–Pull Gradient Methods for Distributed Optimization in Networks (2018, methodology): “There can be multiple variants of the proposed algorithm depending on whether the Adapt-then-Combine (ATC) strategy [40] is used in the x-update and/or the y-update (see Remark 3 in [9] for more details).”
Excess-Risk of Distributed Stochastic Learners (2013, background): “ith positive entries. Moreover, since the matrix Ais leftstochastic and primitive, it has a single eigenvalue at one, and the remaining eigenvalues have magnitude strictly less than one [27, p. 514], [28]. We denote the right eigenvector of Acorresponding to the eigenvalue at one by pand normalize i”
Adaptation, Learning, and Optimization over Networks (2014, methodology): “We shall study distributed solutions in the context of adaptive networks [208, 209, 215], which consist of a collection of agents with adaptation and learning abilities.”
Balancing Communication and Computation in Distributed Optimization (2017, methodology): “In [57], the author propose two algorithms for quadratic problems: CTA (Combine-then-Adapt) and ATC (Adapt-thenCombine).”
Diffusion strategies for adaptation and learning over networks: an examination of distributed strategies and network behavior (2013, methodology): “- -; E/ / (19) Note, for instance, that in the CTA case, the convex combination of the neighborhood weights appears inside the rightmost error term in (19).”
Multitask Diffusion Adaptation Over Networks (2013, background): “Boldface capital letters denote matrices.”
Distributed Policy Evaluation Under Multiple Behavior Strategies (2013, methodology): “In order to find the global saddle-point of the aggregate Lagrangian (31) in a cooperative and stochastic manner, we apply diffusion strategies [19]–[21].”
Adaptive Networks (2014, methodology): “Itis explained in [1] and [11] that, while such selections may be appropriate in some applications, they can nevertheless lead to degraded performance in the context of adaptation and learning over networks [139].”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, unknown): “(ii) Laplacian-based constant edge weight matrix [28, 33],”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, methodology): “The work in [35], [36] utilizes an adapt-then-combine (ATC) strategy [90], [91] of dynamic weighted-average consensus approach [92] to develop a distribute algorithm, termed Aug-DGM algorithm.”
A survey of distributed optimization (2019, methodology): “For the recent review and progress, please refer to the surveys ( Boyd et al., 2011; Nedi ´c, 2015; Nedi ´c & Liu, 2018; Nedi ´c et al., 2018; Sayed, 2014a; Yang & Johansson, 2010 ) and the books ( Bullo, 2017; Giselsson, 2018; Ren & Cao, 2011; Zhu & Martínez, 2015 ).”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “The proposed algorithm is based on the combination of Adapt-then-Combine (ATC) strategy of [59] and the dynamic average consensus for gradient tracking of [77].”
Distributed multi-task classification: a decentralized online learning approach (2017, methodology): “Diffusion methods [12,30] maintain the combination step of consensus learning but evaluate the (sub)gradient information by using the combined learning weights.”
Robust Distributed Estimation by Networked Agents (2017, methodology): “Traditionally in the energy conservation framework [8], [11], [20], one evaluates the weighted variance relation associated with (64) by equating the squared weighted Euclidean norms of both sides with respect to a symmetric nonnegative-definite weighting matrix Σ that we are free to choose, taking ”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, unknown): “(ii) Laplacian-based constant edge weight matrix [28,33],”
Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation Over Adaptive Networks (2012, background): “The second step of (10) is a consultation (combination) step where the intermediate estimates { ψ l,i } from the neighborhood of node k are combined through weights { a l,k } that satisfy (9) to obtain the updated weight estimate w k,i .”