Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks

Abstract

We propose an adaptive 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. 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.

34 pages, 6 figures, to appear in IEEE Transactions on Signal Processing, 2012

References in corpus (7)

• Gossip Algorithms for Distributed Signal Processing
• Sensor Networks with Random Links: Topology Design for Distributed Consensus
• Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs
• Online Sparse System Identification and Signal Reconstruction using Projections onto Weighted ${\ell }_1$ Balls
• Decentralized Maximum Likelihood Estimation for Sensor Networks Composed of Nonlinearly Coupled Dynamical Systems
• Distributed Decision Through Self-Synchronizing Sensor Networks in the Presence of Propagation Delays and Asymmetric Channels
• Data-Distributed Weighted Majority and Online Mirror Descent

Cited by in corpus (132)

• Speeding Up Distributed Machine Learning Using Codes
• Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation over Adaptive Networks
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Federated Learning with Cooperating Devices: A Consensus Approach for Massive IoT Networks
• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
• From Distributed Machine Learning to Federated Learning: A Survey
• Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
• Multitask Diffusion Adaptation over Networks
• Diffusion LMS over Multitask Networks
• Sparse Distributed Learning Based on Diffusion Adaptation
• Distributed Random Projection Algorithm for Convex Optimization
• Diffusion Adaptation over Networks under Imperfect Information Exchange and Non-stationary Data
• Distributed Pareto Optimization via Diffusion Strategies
• A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Distributed Clustering and Learning Over Networks
• Adaptive Penalty-Based Distributed Stochastic Convex Optimization
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
• Distributed Optimization for Smart Cyber-Physical Networks
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Dictionary Learning over Distributed Models
• On the genericity properties in networked estimation: Topology design and sensor placement
• Diffusion LMS Strategies in Sensor Networks with Noisy Input Data
• Proximity Without Consensus in Online Multi-Agent Optimization
• Proximal Multitask Learning over Networks with Sparsity-inducing Coregularization
• Empirical Centroid Fictitious Play: An Approach For Distributed Learning In Multi-Agent Games
• Study of Robust Diffusion Recursive Least Squares Algorithms with Side Information for Networked Agents
• Distributed Nesterov gradient methods over arbitrary graphs
• Distributed Adaptive Learning of Graph Signals
• Diffusion LMS for Multitask Problems with Local Linear Equality Constraints
• Multitask diffusion adaptation over networks with common latent representations
• Privacy-preserving Distributed Machine Learning via Local Randomization and ADMM Perturbation
• Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
• On the Convergence of Decentralized Gradient Descent
• Stability and Performance Limits of Adaptive Primal-Dual Networks
• Estimation of Space-Time Varying Parameters Using a Diffusion LMS Algorithm
• Distributed Decision-Making over Adaptive Networks
• On reducing the communication cost of the diffusion LMS algorithm
• On the Influence of Informed Agents on Learning and Adaptation over Networks
• Resilient Distributed Diffusion in Networks with Adversaries
• Privacy-preserving Incremental ADMM for Decentralized Consensus Optimization
• Convergence and Applications of a Gossip-based Gauss-Newton Algorithm
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Diffusion Adaptation over Multi-Agent Networks with Wireless Link Impairments
• Non-Bayesian Social Learning with Uncertain Models
• Distributed Constrained Recursive Nonlinear Least-Squares Estimation: Algorithms and Asymptotics
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• On Distributed Online Classification in the Midst of Concept Drifts
• Diffusion Leaky Zero Attracting Least Mean Square Algorithm and Its Performance Analysis
• Bayesian Quadratic Network Game Filters
• A proof of uniform convergence over time for a distributed particle filter
• Diffusion Adaptation Strategies for Distributed Estimation over Gaussian Markov Random Fields
• Distributed Gradient Methods with Variable Number of Working Nodes
• Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
• Deep Learning-Based Average Consensus
• Diffusion Estimation Over Cooperative Multi-Agent Networks With Missing Data
• Information-Sharing over Adaptive Networks with Self-interested Agents
• Networked estimation under information constraints
• Diffusion leaky LMS algorithm: analysis and implementation
• Scaling-up Distributed Processing of Data Streams for Machine Learning
• Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
• FADE: Fast and Asymptotically efficient Distributed Estimator for dynamic networks
• A Unified Algorithmic Framework for Distributed Adaptive Signal and Feature Fusion Problems -- Part I: Algorithm Derivation
• Distributed Mirror Descent over Directed Graphs
• Distributed Stochastic Gradient Tracking Methods
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• An introduction to decentralized stochastic optimization with gradient tracking
• On the Learning Behavior of Adaptive Networks - Part I: Transient Analysis
• Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks
• A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization
• Distributed Embodied Evolution over Networks
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis
• Distributed Aggregative Optimization over Multi-Agent Networks
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization
• Information Sharing in Networks of Strategic Agents
• MARL with General Utilities via Decentralized Shadow Reward Actor-Critic
• Consensus Multi-Agent Reinforcement Learning for Volt-VAR Control in Power Distribution Networks
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
• Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework
• Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations
• NEXT: In-Network Nonconvex Optimization
• Asynchronous adaptive networks
• Distributed Multi-task APA over Adaptive Networks Based on Partial Diffusion
• A fast randomized incremental gradient method for decentralized non-convex optimization
• A Distributed Stochastic Gradient Tracking Method
• Asynchronous Adaptation and Learning over Networks --- Part I: Modeling and Stability Analysis
• Communication-Efficient Algorithms For Distributed Optimization
• Finite-Time Error Bounds for Distributed Linear Stochastic Approximation
• Distributed Proximal Algorithms for Multi-Agent Optimization with Coupled Inequality Constraints
• Accelerating Gossip SGD with Periodic Global Averaging
• Distributed Stochastic Nonconvex Optimization and Learning based on Successive Convex Approximation
• Distributed algorithms for solving convex inequalities
• Accelerated Consensus via Min-Sum Splitting
• A general framework for decentralized optimization with first-order methods
• Gradient-Consensus: Linearly Convergent Distributed Optimization Algorithm over Directed Graphs
• A Bregman Splitting Algorithm for Distributed Optimization over Networks
• Geometrical Convergence Rate for Distributed Optimization with Time-Varying Directed Graphs and Uncoordinated Step-Sizes
• Peer-to-Peer Learning Dynamics of Wide Neural Networks
• Heavy-Tail Phenomenon in Decentralized SGD
• Distributed Robust Subspace Recovery
• Distributed Fictitious Play for Optimal Behavior of Multi-Agent Systems with Incomplete Information
• Stochastic Subgradient Algorithms for Strongly Convex Optimization over Distributed Networks
• ELM-Based Distributed Cooperative Learning Over Networks
• Deterministic and Randomized Diffusion based Iterative Generalized Hard Thresholding (DiFIGHT) for Distributed Sparse Signal Recovery
• Distributed Sparse Regression via Penalization
• Diffusion Adaptation Framework for Compressive Sensing Reconstruction
• Graph Balancing for Distributed Subgradient Methods over Directed Graphs
• On the Learning Behavior of Adaptive Networks - Part II: Performance Analysis
• A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks
• Analysis of incremental augmented affine projection algorithm for distributed estimation of complex signals
• Local Thresholding in General Network Graphs
• Distributed Adaptive Signal Fusion for Fractional Programs
• Distributed Estimation for Adaptive Networks Based on Serial-Inspired Diffusion
• Nash Equilibrium Computation in Subnetwork Zero-Sum Games with Switching Communications
• Distributed Optimization Using the Primal-Dual Method of Multipliers
• Distributed Policy Evaluation Under Multiple Behavior Strategies
• An Improved Self-Organizing Diffusion Mobile Adaptive Network for Pursuing a Target
• Diffusion LMS for clustered multitask networks
• A Class of Diffusion Algorithms with Logarithmic Cost over Adaptive Sparse Volterra Network
• Study of Diffusion Normalized Least Mean M-estimate Algorithms
• Maximum Total Correntropy Diffusion Adaptation over Networks with Noisy Links
• Study of Robust Distributed Diffusion RLS Algorithms with Side Information for Adaptive Networks
• Steady-state Performance of Incremental LMS Strategies For Parameter Estimation Over Fading Wireless Channels
• On the Asymptotic Bias of the Diffusion-Based Distributed Pareto Optimization