View all Seminars  |  Download ICal for this event

Efficient Intervention Design for Learning Causal DAGs

Series: Theory Seminar

Speaker: Dr. Karthikeyan Shanmugam Research Staff Member IBM Research AI group New York

Date/Time: Sep 17 16:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

Network of cause effect relationships between measured variables is modeled as a causal DAG (Directed Acyclic Graph). In this talk, we focus on efficient adaptive intervention design for learning a causal DAG, with no latent confounders, given the observational equivalence class it belongs to as an input. We first consider equivalence class inputs whose skeleton is a tree. We consider a Bayesian framework where a prior over all directed trees is updated based on the outcome of every single node intervention each of which is adaptively designed based on current posterior. We provide an efficient algorithm that requires interventions that is within a factor of 2 from the best adaptive algorithm. We also show that information greedy approaches are exponentially sub-optimal in terms of the optimal number of interventions required. The main technical tool is a simple greedy algorithm that myopically optimizes a centrality measure on the skeleton of the true causal tree.
We generalize and extend the above approach for adaptive interventional design to learn an arbitrary causal DAGs given its equivalence class. We show that the half the maximum clique size is an instance specific fundamental lower bound for any algorithm to even verify the DAG structure through interventions given the equivalence class. Under mild assumptions on the equivalence class, we provide an adaptive algorithm inspired by the algorithm on causal trees that requires interventions that matches the optimal number of interventions up to a multiplicative logarithmic factor in the number of maximal cliques.
Microsoft Teams Link:

For more details about the seminar please visit the website at

Speaker Bio:

Host Faculty: Dr. Rahul Saladi