Distributed Detection: Finite-Time Analysis and Impact of Network Topology

By Shahin Shahrampour, Alexander Rakhlin, Ali Jadbabaie. 2014

116 citations recorded by the source corpus.

This paper addresses the problem of distributed detection in multi-agent networks. Agents receive private signals about an unknown state of the world. The underlying state is globally identifiable, yet informative signals may be dispersed throughout the network. Using an optimization-based framework, we develop an iterative local strategy for updating individual beliefs. In contrast to the existing literature which focuses on asymptotic learning, we provide a finite-time analysis. Furthermore, we introduce a Kullback-Leibler cost to compare the efficiency of the algorithm to its centralized counterpart. Our bounds on the cost are expressed in terms of network size, spectral gap, centrality of each agent and relative entropy of agents' signal structures. A key observation is that distributing more informative signals to central agents results in a faster learning rate. Furthermore, optimizing the weights, we can speed up learning by improving the spectral gap. We also quantify the effect of link failures on learning speed in symmetric networks. We finally provide numerical simulations for our method which verify our theoretical results.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

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

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Decentralized Bayesian Learning over Graphs (2019, neutral): “We partition the MNIST dataset into two subsets so that the central agent dataset has all images of labels [2 , . . . , 9] and edge agents has all images of labels [0 , 1] .”
Peer-to-peer Federated Learning on Graphs (2019, methodology): “…in statistics, economics, and operations research and encompasses canonical problems of consensus DeGroot (1974), belief propagation (Olfati-Saber et al., 2005), and distributed hypothesis testing (Jad-babaie et al., 2013; Nedi ´ c et al., 2015; Shahrampour et al., 2016; Lalitha et al., 2018).”
Defending non-Bayesian learning against adversarial attacks (2016, neutral): “In contrast, the corresponding matrices in [13,14,16,18] do not depend on the exchanged messages.”
Social learning and distributed hypothesis testing (2014, result): “In a simultaneous and independent works [7] and [8], a slight variant of our learning rule in [9] is proposed and similar convergence results are obtained.”
Distributed Online Optimization in Dynamic Environments Using Mirror Descent (2016, background): “In the same context, replacing the arithmetic averaging by geometric averaging in (8b), one can recover faster learning updates as in [4], [5], and [36].”
Nonasymptotic convergence rates for cooperative learning over time-varying directed graphs (2014, background): “In [19], similar probabilistic bounds for the rate of convergence are derived for fixed graphs and comparisons with the centralized version of the learning rule are provided.”