Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks

Published on Aug 1, 2012in IEEE Transactions on Signal Processing5.028
· DOI :10.1109/TSP.2012.2198470
Jianshu Chen28
Estimated H-index: 28
(UCLA: University of California, Los Angeles),
Ali H. Sayed86
Estimated H-index: 86
(UCLA: University of California, Los Angeles)
Sources
Abstract
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.
📖 Papers frequently viewed together
312 Citations
296 Citations
631 Citations
References74
Newest
We survey incremental methods for minimizing a sum P m=1 fi(x) consisting of a large number of convex component functions fi. Our methods consist of iterations applied to single components, and have proved very effective in practice. We introduce a unified algorithmic framework for a variety of such methods, some involving gradient and subgradient iterations, which are known, and some involving combinations of subgradient and proximal methods, which are new and offer greater flexibility in explo...
326 Citations
#1Sheng-Yuan Tu (UCLA: University of California, Los Angeles)H-Index: 14
#2Ali H. Sayed (UCLA: University of California, Los Angeles)H-Index: 86
Adaptive networks consist of a collection of nodes that 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 performance of two distributed estimation strategies: diffusion and consensus. Diffusion strategies allow information to diffuse more thoroughly through the network. The analysis in the paper confirms that this property has a favorable effect on the evolution of th...
12 CitationsSource
#1Jianshu Chen (UCLA: University of California, Los Angeles)H-Index: 28
#2Ali H. Sayed (UCLA: University of California, Los Angeles)H-Index: 86
We consider solving multi-objective optimization problems in a distributed manner over a network of nodes. The problem is equivalent to optimizing a global cost that is the sum of individual components. Diffusion adaptation enables the nodes to cooperate locally through in-network processing in order to approach Pareto-optimality. We analyze the mean-square-error performance of the diffusion strategy and show that, at steady-state, all nodes can be made to approach a Pareto-optimal solution.
17 CitationsSource
Mar 25, 2012 in ICASSP (International Conference on Acoustics, Speech, and Signal Processing)
#1Paolo Di Lorenzo (Sapienza University of Rome)H-Index: 16
#1Paolo Di Lorenzo (Sapienza University of Rome)H-Index: 20
Last. Ali H. Sayed (UCLA: University of California, Los Angeles)H-Index: 86
view all 3 authors...
The goal of this paper is to propose diffusion LMS techniques for distributed estimation over adaptive networks, which are able to exploit sparsity in the underlying system model. The approach relies on convex regularization, common in compressive sensing, to improve the performance of the diffusion strategies. We provide convergence and performance analysis of the proposed method, showing under what conditions it outperforms the unregularized diffusion version. Simulation results illustrate the...
24 CitationsSource
Mar 25, 2012 in ICASSP (International Conference on Acoustics, Speech, and Signal Processing)
#1Jianshu Chen (UCLA: University of California, Los Angeles)H-Index: 28
#2Ali H. Sayed (UCLA: University of California, Los Angeles)H-Index: 86
We derive 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 the sum of individual components, and diffusion adaptation is used to enable the nodes to cooperate locally through in-network processing in order to solve the desired optimization problem. We analyze the mean-square-error performance of the algorithm, including its transient and steady-state behavior. We illustrate one applicatio...
5 CitationsSource
#1Jinchao Li (UCLA: University of California, Los Angeles)H-Index: 2
#2Ali H. Sayed (UCLA: University of California, Los Angeles)H-Index: 86
Honeybees swarm when they move to a new site for their hive. During the process of swarming, their behavior can be analyzed by classifying them as informed bees or uninformed bees, where the informed bees have some information about the destination while the uninformed bees follow the informed bees. The swarm's movement can be viewed as a network of mobile nodes with asymmetric information exchange about their destination. In these networks, adaptive and mobile agents share information on the fl...
38 CitationsSource
#1Jianshu Chen (UCLA: University of California, Los Angeles)H-Index: 28
#2Sheng-Yuan Tu (UCLA: University of California, Los Angeles)H-Index: 14
Last. Ali H. Sayed (UCLA: University of California, Los Angeles)H-Index: 86
view all 3 authors...
We develop an iterative diffusion mechanism to optimize a global cost function in a distributed manner over a network of nodes. The cost function is assumed to consist of a collection of individual components, and diffusion strategy allows the nodes to cooperate and diffuse information in real-time. Compared to incremental methods, diffusion methods do not require the use of a cyclic path over the nodes and are more robust to node and link failure.
13 CitationsSource
#1Ceyhun Eksin (UPenn: University of Pennsylvania)H-Index: 12
#2Alejandro Ribeiro (UPenn: University of Pennsylvania)H-Index: 58
We study a distributed model for optimizing a sum of convex objective functions corresponding to agents in the network. At random times, agents execute actions based on heuristic rational rules considering only local information. Heuristic rational rules are probabilistic and their expectation yields the actual optimal action. Under heuristic rational rule iterations, it is shown that global network cost comes within a close vicinity of the optimal value infinitely often with probability 1. Furt...
1 CitationsSource
#1Zaid J. Towfic (UCLA: University of California, Los Angeles)H-Index: 12
#2Jianshu Chen (UCLA: University of California, Los Angeles)H-Index: 28
Last. Ali H. Sayed (UCLA: University of California, Los Angeles)H-Index: 86
view all 3 authors...
In large ad-hoc networks, classification tasks such as spam filtering, multi-camera surveillance, and advertising have been traditionally implemented in a centralized manner by means of fusion centers. These centers receive and process the information that is collected from across the network. In this paper, we develop a decentralized adaptive strategy for information processing and apply it to the task of estimating the parameters of a Gaussian-mixture-model (GMM). The proposed technique employ...
29 CitationsSource
#1Symeon Chouvardas (UoA: National and Kapodistrian University of Athens)H-Index: 10
#2Konstantinos Slavakis (UoP: University of Peloponnese)H-Index: 23
Last. Sergios Theodoridis (UoA: National and Kapodistrian University of Athens)H-Index: 43
view all 3 authors...
In this paper, the problem of adaptive distributed learning in diffusion networks is considered. The algorithms are developed within the convex set theoretic framework. More specifically, they are based on computationally simple geometric projections onto closed convex sets. The paper suggests a novel combine-project-adapt protocol for cooperation among the nodes of the network; such a protocol fits naturally with the philosophy that underlies the projection-based rationale. Moreover, the possib...
152 CitationsSource
Cited By490
Newest
Source
#1Babak BarazandehH-Index: 9
#2Tianjian Huang (SC: University of Southern California)
Last. George Michailidis (UF: University of Florida)H-Index: 53
view all 3 authors...
Min-max saddle point games have recently been intensely studied, due to their wide range of applications, including training Generative Adversarial Networks~(GANs). However, most of the recent efforts for solving them are limited to special regimes such as convex-concave games. Further, it is customarily assumed that the underlying optimization problem is solved either by a single machine or in the case of multiple machines connected in centralized fashion, wherein each one communicates with a c...
#1Yunxiang Zhang (University of Electronic Science and Technology of China)
#2Yuyang Zhao (University of Electronic Science and Technology of China)
Last. Rui Xue (Beihang University)
view all 4 authors...
Most of the cost functions of adaptive filtering algorithms include the square error, which depends on the current error signal. When the additive noise is impulsive, we can expect that the square error will be very large. By contrast, the cross error, which is the correlation of the error signal and its delay, may be very small. Based on this fact, we propose a new cost function called the mean square cross error for adaptive filters, and provide the mean value and mean square performance analy...
Source
#2Azam KhaliliH-Index: 12
Last. Saeid Sanei (NTU: Nottingham Trent University)H-Index: 31
view all 4 authors...
In this letter a robust incremental adaptation algorithm is presented to solve distributed estimation for a Hamiltonian network, where the measurements at each node may be corrupted by heavy-tailed impulsive noise. In the proposed algorithm, each node employs an error-nonlinearity into the update equation to mitigate the detrimental effects of impulsive noise. Moreover, the algorithm estimates both the optimal error non-linearity and the unknown parameter together, which in turn, obviates the re...
1 CitationsSource
#1Hao Chen (BIT: Beijing Institute of Technology)H-Index: 9
#2Jianan Wang (BIT: Beijing Institute of Technology)H-Index: 7
Last. Ming Xin (MU: University of Missouri)H-Index: 22
view all 5 authors...
Abstract null null In this paper, a distributed diffusion unscented Kalman null filtering algorithm null null based on covariance intersection strategy (DDUKF-CI) is proposed for target tracking with intermittent measurements. By virtue of the pseudo null measurement matrix , the standard unscented Kalman filtering (UKF) with intermittent observations is transformed to the information form for the diffusion algorithm to fuse intermediate information from neighbors and improve the estimation perf...
Source
#1Qing Shi (SWU: Southwest University)H-Index: 3
#2Feng ChenH-Index: 4
Last. Shukai Duan (SWU: Southwest University)H-Index: 28
view all 4 authors...
Abstract With increasing research on distributed processing in networks, adaptive learning strategies have gradually attracted researchers’ attention. The traditional adaptive learning strategy mainly aims at a single task unchanged over time, while real networks often entail multitasks scenarios with tasks that change over time. Furthermore, although cooperation among agents is beneficial for single task time-invariant networks, agents’ indiscriminate cooperation in time-varying multitask netwo...
Source
In this work, we introduce ADAPD, \textbf{A}\textbf{D}centr\textbf{A}ized \textbf{P}imal-\textbf{D}al algorithmic framework for solving non-convex and smooth consensus optimization problems over a network of distributed agents. ADAPD makes use of an inexact ADMM-type update. During each iteration, each agent first inexactly solves a local strongly convex subproblem and then performs a neighbor communication while updating a set of dual variables. Two variations to ADAPD are presen...
#1Muhammad I. Qureshi (Tufts University)H-Index: 3
#2Ran Xin (CMU: Carnegie Mellon University)H-Index: 12
Last. Usman A. Khan (Tufts University)H-Index: 42
view all 4 authors...
In this letter, we study decentralized stochastic optimization to minimize a sum of smooth and strongly convex cost functions when the functions are distributed over a directed network of nodes. In contrast to the existing work, we use gradient tracking to improve certain aspects of the resulting algorithm. In particular, we propose the S-ADDOPT algorithm that assumes a stochastic first-order oracle at each node and show that for a constant step-size \alpha , each node converges linearly insi...
8 CitationsSource
#1Yan Linfang (HUST: Huazhong University of Science and Technology)H-Index: 1
#2Xia Chen (HUST: Huazhong University of Science and Technology)H-Index: 11
Last. Yin Chen (University of Strathclyde)H-Index: 5
view all 5 authors...
Abstract High penetration of distributed energy resources will bring extreme challenges to the existing centralized energy management approach as the system becomes much more decentralized than before. To address this issue, this paper proposes a fully distributed algorithm based on diffusion strategy to solve the optimal energy management. First, the optimal resource management is modelled as a social welfare maximization problem with considering the generation cost, users’ utility and network ...
Source
Source