Social Learning and Distributed Hypothesis Testing

This paper considers a problem of distributed hypothesis testing over a network. Individual nodes in a network receive noisy local (private) observations whose distribution is parameterized by a discrete parameter (hypothesis). The marginals of the joint observation distribution conditioned on each...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2018-09, Vol.64 (9), p.6161-6179
Main Authors: Lalitha, Anusha, Javidi, Tara, Sarwate, Anand D.
Format: Article
Language:English
Subjects:
Bayes methods
Bayesian analysis
Conditioning
Convergence
Distributed algorithms
Divergence
Estimation
Heuristic algorithms
Hypothesis testing
large deviation principle
Message passing
Nodes
Parameters
Probability distribution
rate of learning
Rejection
Testing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper considers a problem of distributed hypothesis testing over a network. Individual nodes in a network receive noisy local (private) observations whose distribution is parameterized by a discrete parameter (hypothesis). The marginals of the joint observation distribution conditioned on each hypothesis are known locally at the nodes, but the true parameter/hypothesis is not known. An update rule is analyzed in which nodes first perform a Bayesian update of their belief (distribution estimate) of each hypothesis based on their local observations, communicate these updates to their neighbors, and then perform a "non-Bayesian" linear consensus using the log-beliefs of their neighbors. Under mild assumptions, we show that the belief of any node on a wrong hypothesis converges to zero exponentially fast. We characterize the exponential rate of learning, which we call the network divergence, in terms of the nodes' influence of the network and the divergences between the observations' distributions. For a broad class of observation statistics which includes distributions with unbounded support such as Gaussian mixtures, we show that rate of rejection of wrong hypothesis satisfies a large deviation principle, i.e., the probability of sample paths on which the rate of rejection of wrong hypothesis deviates from the mean rate vanishes exponentially fast and we characterize the rate function in terms of the nodes' influence of the network and the local observation models.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2018.2837050