Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks

By Jianshu Chen, Ali H. Sayed. IEEE Transactions on Signal Processing, 2011

708 citations recorded by the source corpus.

We propose an adaptive diffusion mechanism to optimize global cost functions in a distributed manner over a network of nodes. The cost function is assumed to consist of a collection of individual components. Diffusion adaptation allows the nodes to cooperate and diffuse information in real-time; it also helps alleviate the effects of stochastic gradient noise and measurement noise through a continuous learning process. We analyze the mean-square-error performance of the algorithm in some detail, including its transient and steady-state behavior. We also apply the diffusion algorithm to two problems: distributed estimation with sparse parameters and distributed localization. Compared to well-studied incremental methods, diffusion methods do not require the use of a cyclic path over the nodes and are robust to node and link failure. Diffusion methods also endow networks with adaptation abilities that enable the individual nodes to continue learning even when the cost function changes with time. Examples involving such dynamic cost functions with moving targets are common in the context of biological networks.

Subfields: Computational Mechanics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/4b1deda730399d2d2870a2d4d31120b297183f34

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

Citations in the corpus

From distributed machine learning to federated learning: a survey (2021, positive): “However, ABC is robust [152], and it converges fast in terms of iterations by exploiting its large learning rate.”
Federated Learning With Cooperating Devices: A Consensus Approach for Massive IoT Networks (2019, methodology): “The negotiation stage (13)–(14) is similar to the diffusion strategy proposed in [30] and [31].”
Adaptive Networks (2014, methodology): “…we can readily establish the identity Using the fact that P is primitive, the following low-rank approximation can be derived [1], [16], [32], [58]: where Substituting (114e) into (114d), we arrive, after some algebra, at expression (112) for MSD dist ; av [1], [16], [127]; similarly…”
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.”
NEXT: In-Network Nonconvex Optimization (2016, background): “Thus, the least squares estimator f or he target positionsx , (xt) NT t=1 is the solution of the following nonconvexoptimization problem [17]:”
Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation Over Adaptive Networks (2012, methodology): “, [30], [ 40] and the references therein.”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, methodology): “Our work here contributes to the growing literature on distributed methods for optimization over networks [5], [9], [12], [14]–[16], [19]–[23], [28], [32], [34], [40], [43].”
A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent (2019, background): “1) find applications in multi-agent target seeking [32, 8], distributed machine learning [13, 24, 10, 2, 46, 1, 4], and wireless networks [9, 20, 2], among other scenarios.”
Excess-Risk of Distributed Stochastic Learners (2013, methodology): “ the algorithm will achieve the Cram´er-Rao convergence rate up to some constants that do not depend on the number of nodes Nor the iteration number i. A. Diffusion Strategy Following the approach of [9], it is possible to derive the diffusion strategy for the distributed evaluation of estimates w k”
A review of cooperative multi-agent deep reinforcement learning (2019, background): “Then, inspiring from [21], they proposed a diffusion-based distributed GTD algorithm.”
Efficient Distributed Online Prediction and Stochastic Optimization With Approximate Distributed Averaging (2014, positive): “For this reason, gossip-based distributed optimization methods have recently received considerable attention [5,10,13,17,24,33].”
Multitask Diffusion Adaptation Over Networks (2013, background): “Its performance was further examined under various scenarios and the algorithms applied to a variety of inference and estimation problems in [18], [19], [21]–[30].”
Distributed Network Optimization With Heuristic Rational Agents (2012, methodology): “Distributed network optimization is a common solution method for estimation and detection problems in wireless sensor networks (WSNs) [1]–[7].”
Consensus-based distributed optimization: Practical issues and applications in large-scale machine learning (2012, background): “Among numerous alternatives, a significant amount of research has focused on developing consensus-based algorithms [2]–[7] which combine some version of local optimization with a distributed consensus”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, methodology): “Problems in the form of (1) ﬁnd applications in multiagent target seeking [1], distributed machine learning [2]–[8], and wireless networks [5], [9], [10], among other scenarios.”
Distributed Policy Evaluation Under Multiple Behavior Strategies (2013, methodology): “We choose theadapt-then-combine(ATC) diffusion variant for distributed optimization over networks [17], [18], [45].”