Timezone: »
We consider testing and learning problems on causal Bayesian networks as defined by Pearl (Pearl, 2009). Given a causal Bayesian network M on a graph with n discrete variables and bounded in-degree and bounded ``confounded components'', we show that O(log n) interventions on an unknown causal Bayesian network X on the same graph, and O(n/epsilon^2) samples per intervention, suffice to efficiently distinguish whether X=M or whether there exists some intervention under which X and M are farther than epsilon in total variation distance. We also obtain sample/time/intervention efficient algorithms for: (i) testing the identity of two unknown causal Bayesian networks on the same graph; and (ii) learning a causal Bayesian network on a given graph. Although our algorithms are non-adaptive, we show that adaptivity does not help in general: Omega(log n) interventions are necessary for testing the identity of two unknown causal Bayesian networks on the same graph, even adaptively. Our algorithms are enabled by a new subadditivity inequality for the squared Hellinger distance between two causal Bayesian networks.
Author Information
Jayadev Acharya (Cornell University)
Arnab Bhattacharyya (National University of Singapore & Indian Institute of Science)
Constantinos Daskalakis (MIT)
Saravanan Kandasamy (Tata Institute of Fundamental Research)
More from the Same Authors
-
2022 : Hidden Poison: Machine Unlearning Enables Camouflaged Poisoning Attacks »
Jimmy Di · Jack Douglas · Jayadev Acharya · Gautam Kamath · Ayush Sekhari -
2022 : Hidden Poison: Machine unlearning enables camouflaged poisoning attacks »
Jimmy Di · Jack Douglas · Jayadev Acharya · Gautam Kamath · Ayush Sekhari -
2021 : Spotlight 4: Estimation of Standard Asymmetric Auction Models »
Yeshwanth Cherapanamjeri · Constantinos Daskalakis · Andrew Ilyas · Emmanouil Zampetakis -
2021 Poster: Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition »
Jayadev Acharya · Clement Canonne · Yuhan Liu · Ziteng Sun · Himanshu Tyagi -
2021 Poster: Information-constrained optimization: can adaptive processing of gradients help? »
Jayadev Acharya · Clement Canonne · Prathamesh Mayekar · Himanshu Tyagi -
2021 Poster: Remember What You Want to Forget: Algorithms for Machine Unlearning »
Ayush Sekhari · Jayadev Acharya · Gautam Kamath · Ananda Theertha Suresh -
2021 Poster: Optimal Rates for Nonparametric Density Estimation under Communication Constraints »
Jayadev Acharya · Clement Canonne · Aditya Vikram Singh · Himanshu Tyagi -
2019 Poster: Estimating Entropy of Distributions in Constant Space »
Jayadev Acharya · Sourbh Bhadane · Piotr Indyk · Ziteng Sun -
2018 Poster: Differentially Private Testing of Identity and Closeness of Discrete Distributions »
Jayadev Acharya · Ziteng Sun · Huanyu Zhang -
2018 Spotlight: Differentially Private Testing of Identity and Closeness of Discrete Distributions »
Jayadev Acharya · Ziteng Sun · Huanyu Zhang