Learning and Testing Causal Models with Interventions

Saravanan Kandasamy
Piyush Srivastava
Tuesday, 16 Oct 2018, 14:00 to 15:00
A-201 (STCS Seminar Room)
Abstract: We consider testing and learning problems on causal Bayesian networks as defined by Pearl.  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 (joint work with: Jayadev Acharya, Arnab Bhattacharyya and Constantinos  Daskalakis).