Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs

Abstract

The paper considers gossip distributed estimation of a (static) distributed random field (a.k.a., large scale unknown parameter vector) observed by sparsely interconnected sensors, each of which only observes a small fraction of the field. We consider linear distributed estimators whose structure combines the information \emph{flow} among sensors (the \emph{consensus} term resulting from the local gossiping exchange among sensors when they are able to communicate) and the information \emph{gathering} measured by the sensors (the \emph{sensing} or \emph{innovations} term.) This leads to mixed time scale algorithms--one time scale associated with the consensus and the other with the innovations. The paper establishes a distributed observability condition (global observability plus mean connectedness) under which the distributed estimates are consistent and asymptotically normal. We introduce the distributed notion equivalent to the (centralized) Fisher information rate, which is a bound on the mean square error reduction rate of any distributed estimator; we show that under the appropriate modeling and structural network communication conditions (gossip protocol) the distributed gossip estimator attains this distributed Fisher information rate, asymptotically achieving the performance of the optimal centralized estimator. Finally, we study the behavior of the distributed gossip estimator when the measurements fade (noise variance grows) with time; in particular, we consider the maximum rate at which the noise variance can grow and still the distributed estimator being consistent, by showing that, as long as the centralized estimator is consistent, the distributed estimator remains consistent.

Submitted for publication, 30 pages

References in corpus (4)

• Gossip Algorithms for Distributed Signal Processing
• Sensor Networks with Random Links: Topology Design for Distributed Consensus
• Gossip and Distributed Kalman Filtering: Weak Consensus under Weak Detectability
• Weight Optimization for Consensus Algorithms with Correlated Switching Topology

Cited by in corpus (58)

• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation over Adaptive Networks
• Diffusion Adaptation over Networks under Imperfect Information Exchange and Non-stationary Data
• Distributed Pareto Optimization via Diffusion Strategies
• $QD$-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations
• Consensus+Innovations Distributed Kalman Filter with Optimized Gains
• Performance Limits for Distributed Estimation Over LMS Adaptive Networks
• Resilient Distributed Estimation Through Adversary Detection
• Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Diffusion LMS Strategies in Sensor Networks with Noisy Input Data
• Proximal Multitask Learning over Networks with Sparsity-inducing Coregularization
• Empirical Centroid Fictitious Play: An Approach For Distributed Learning In Multi-Agent Games
• Distributed Detection over Noisy Networks: Large Deviations Analysis
• Supervised Learning Under Distributed Features
• Diffusion-Based Adaptive Distributed Detection: Steady-State Performance in the Slow Adaptation Regime
• 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
• Resilient Distributed Parameter Estimation with Heterogeneous Data
• On the Influence of Informed Agents on Learning and Adaptation over Networks
• 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
• Networked Signal and Information Processing
• Bayesian Quadratic Network Game Filters
• Diffusion Estimation Over Cooperative Multi-Agent Networks With Missing Data
• Information-Sharing over Adaptive Networks with Self-interested Agents
• Accelerated Distributed Dual Averaging over Evolving Networks of Growing Connectivity
• Local Tomography of Large Networks under the Low-Observability Regime
• $\mathcal{C}\mathcal{I}\mathcal{R}\mathcal{FE}$: A Distributed Random Fields Estimator
• Coordinate-Descent Diffusion Learning by Networked Agents
• Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
• FADE: Fast and Asymptotically efficient Distributed Estimator for dynamic networks
• Distributed Inference for Relay-Assisted Sensor Networks With Intermittent Measurements Over Fading Channels
• On the Learning Behavior of Adaptive Networks - Part I: Transient Analysis
• Communication Optimality Trade-offs For Distributed Estimation
• Distributed Universal Adaptive Networks
• Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis
• Information Sharing in Networks of Strategic Agents
• Asynchronous adaptive networks
• Asynchronous Adaptation and Learning over Networks --- Part I: Modeling and Stability Analysis
• Asynchronous Adaptation and Learning over Networks - Part II: Performance Analysis
• Distributed Parameter Estimation Under Event-triggered Communications
• Resilient Distributed Recovery of Large Fields
• Dynamic Average Diffusion with randomized Coordinate Updates
• On the Learning Behavior of Adaptive Networks - Part II: Performance Analysis
• Topology Inference over Networks with Nonlinear Coupling
• Steady-state Analysis of a Neural-cognition Based Human-social Behavior Model
• Distributed Estimation using Bayesian Consensus Filtering
• On Decentralized Estimation with Active Queries
• Distributed Estimation Via a Roaming Token
• Distributed Policy Evaluation Under Multiple Behavior Strategies
• When Adaptive Diffusion Algorithm Converges to True Parameter?
• Steady-state Performance of Incremental LMS Strategies For Parameter Estimation Over Fading Wireless Channels
• How Agreement and Disagreement Evolve over Random Dynamic Networks
• Secure distributed filtering for unstable dynamics under compromised observations
• Resilient Distributed Field Estimation