Timezone: »
Poster
Learning Causal Graphs with Small Interventions
Karthikeyan Shanmugam · Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath
We consider the problem of learning causal networks with interventions, when each intervention is limited in size under Pearl's Structural Equation Model with independent errors (SEM-IE). The objective is to minimize the number of experiments to discover the causal directions of all the edges in a causal graph. Previous work has focused on the use of separating systems for complete graphs for this task. We prove that any deterministic adaptive algorithm needs to be a separating system in order to learn complete graphs in the worst case. In addition, we present a novel separating system construction, whose size is close to optimal and is arguably simpler than previous work in combinatorics. We also develop a novel information theoretic lower bound on the number of interventions that applies in full generality, including for randomized adaptive learning algorithms. For general chordal graphs, we derive worst case lower bounds on the number of interventions. Building on observations about induced trees, we give a new deterministic adaptive algorithm to learn directions on any chordal skeleton completely. In the worst case, our achievable scheme is an $\alpha$-approximation algorithm where $\alpha$ is the independence number of the graph. We also show that there exist graph classes for which the sufficient number of experiments is close to the lower bound. In the other extreme, there are graph classes for which the required number of experiments is multiplicatively $\alpha$ away from our lower bound. In simulations, our algorithm almost always performs very close to the lower bound, while the approach based on separating systems for complete graphs is significantly worse for random chordal graphs.
Author Information
Karthikeyan Shanmugam (UT Austin)
Murat Kocaoglu (UT Austin)
Alex Dimakis (University of Texas, Austin)
Sriram Vishwanath (UT Austin)
More from the Same Authors
-
2020 Poster: SMYRF - Efficient Attention using Asymmetric Clustering »
Giannis Daras · Nikita Kitaev · Augustus Odena · Alexandros Dimakis -
2020 Poster: Applications of Common Entropy for Causal Inference »
Murat Kocaoglu · Sanjay Shakkottai · Alexandros Dimakis · Constantine Caramanis · Sriram Vishwanath -
2020 Poster: Exactly Computing the Local Lipschitz Constant of ReLU Networks »
Matt Jordan · Alexandros Dimakis -
2020 Poster: Robust compressed sensing using generative models »
Ajil Jalal · Liu Liu · Alexandros Dimakis · Constantine Caramanis -
2019 Workshop: Information Theory and Machine Learning »
Shengjia Zhao · Jiaming Song · Yanjun Han · Kristy Choi · Pratyusha Kalluri · Ben Poole · Alexandros Dimakis · Jiantao Jiao · Tsachy Weissman · Stefano Ermon -
2019 Workshop: Solving inverse problems with deep networks: New architectures, theoretical foundations, and applications »
Reinhard Heckel · Paul Hand · Richard Baraniuk · Joan Bruna · Alexandros Dimakis · Deanna Needell -
2019 Poster: Inverting Deep Generative models, One layer at a time »
Qi Lei · Ajil Jalal · Inderjit Dhillon · Alexandros Dimakis -
2019 Poster: Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes »
Matt Jordan · Justin Lewis · Alexandros Dimakis -
2019 Poster: Primal-Dual Block Generalized Frank-Wolfe »
Qi Lei · JIACHENG ZHUO · Constantine Caramanis · Inderjit Dhillon · Alexandros Dimakis -
2019 Poster: Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models »
Shanshan Wu · Sujay Sanghavi · Alexandros Dimakis -
2019 Spotlight: Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models »
Shanshan Wu · Sujay Sanghavi · Alexandros Dimakis -
2019 Poster: Sample Efficient Active Learning of Causal Trees »
Kristjan Greenewald · Dmitriy Katz · Karthikeyan Shanmugam · Sara Magliacane · Murat Kocaoglu · Enric Boix Adsera · Guy Bresler -
2019 Poster: Learning Distributions Generated by One-Layer ReLU Networks »
Shanshan Wu · Alexandros Dimakis · Sujay Sanghavi -
2019 Poster: Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions »
Murat Kocaoglu · Amin Jaber · Karthikeyan Shanmugam · Elias Bareinboim -
2018 Poster: Experimental Design for Cost-Aware Learning of Causal Graphs »
Erik Lindgren · Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath -
2017 Workshop: NIPS Highlights (MLTrain), Learn How to code a paper with state of the art frameworks »
Alexandros Dimakis · Nikolaos Vasiloglou · Guy Van den Broeck · Alexander Ihler · Assaf Araki -
2017 Poster: Experimental Design for Learning Causal Graphs with Latent Variables »
Murat Kocaoglu · Karthikeyan Shanmugam · Elias Bareinboim -
2017 Poster: Streaming Weak Submodularity: Interpreting Neural Networks on the Fly »
Ethan Elenberg · Alexandros Dimakis · Moran Feldman · Amin Karbasi -
2017 Oral: Streaming Weak Submodularity: Interpreting Neural Networks on the Fly »
Ethan Elenberg · Alexandros Dimakis · Moran Feldman · Amin Karbasi -
2017 Poster: Model-Powered Conditional Independence Test »
Rajat Sen · Ananda Theertha Suresh · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai -
2016 Poster: Leveraging Sparsity for Efficient Submodular Data Summarization »
Erik Lindgren · Shanshan Wu · Alexandros Dimakis -
2016 Poster: Single Pass PCA of Matrix Products »
Shanshan Wu · Srinadh Bhojanapalli · Sujay Sanghavi · Alexandros Dimakis -
2015 Poster: Orthogonal NMF through Subspace Exploration »
Megasthenis Asteris · Dimitris Papailiopoulos · Alexandros Dimakis -
2015 Poster: Sparse PCA via Bipartite Matchings »
Megasthenis Asteris · Dimitris Papailiopoulos · Anastasios Kyrillidis · Alexandros Dimakis -
2014 Poster: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alexandros Dimakis · Adam Klivans -
2014 Poster: On the Information Theoretic Limits of Learning Ising Models »
Rashish Tandon · Karthikeyan Shanmugam · Pradeep Ravikumar · Alexandros Dimakis -
2014 Oral: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alexandros Dimakis · Adam Klivans