TY - GEN
T1 - Lower Bounds on Information Requirements for Causal Network Inference
AU - Kang, Xiaohan
AU - Hajek, Bruce
N1 - Funding Information:
This material is based upon work supported by the National Science Foundation under Grant No. CCF 19-00636.
Publisher Copyright:
© 2021 IEEE.
PY - 2021/7/12
Y1 - 2021/7/12
N2 - Recovery of the causal structure of dynamic networks from noisy measurements has long been a problem of intense interest across many areas of science and engineering. Many algorithms have been proposed, but there is no work that compares the performance of the algorithms to converse bounds in a non-asymptotic setting. As a step to address this problem, this paper gives lower bounds on the error probability for causal network support recovery in a linear Gaussian setting. The bounds are based on the use of the Bhattacharyya coefficient for binary hypothesis testing problems with mixture probability distributions. Comparison of the bounds and the performance achieved by two representative recovery algorithms are given for sparse random networks based on the Erdős-Rényi model.
AB - Recovery of the causal structure of dynamic networks from noisy measurements has long been a problem of intense interest across many areas of science and engineering. Many algorithms have been proposed, but there is no work that compares the performance of the algorithms to converse bounds in a non-asymptotic setting. As a step to address this problem, this paper gives lower bounds on the error probability for causal network support recovery in a linear Gaussian setting. The bounds are based on the use of the Bhattacharyya coefficient for binary hypothesis testing problems with mixture probability distributions. Comparison of the bounds and the performance achieved by two representative recovery algorithms are given for sparse random networks based on the Erdős-Rényi model.
UR - http://www.scopus.com/inward/record.url?scp=85115061011&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115061011&partnerID=8YFLogxK
U2 - 10.1109/ISIT45174.2021.9518005
DO - 10.1109/ISIT45174.2021.9518005
M3 - Conference contribution
AN - SCOPUS:85115061011
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 754
EP - 759
BT - 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2021 IEEE International Symposium on Information Theory, ISIT 2021
Y2 - 12 July 2021 through 20 July 2021
ER -