# Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning

arXiv: https://arxiv.org/abs/2105.14024 · HTML: https://mlsanity.com/paper/2105.14024/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 28 May 2021.

## Builds on (most cited first, 15 of 15)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Permutation-based Causal Inference Algorithms with Interventions](https://mlsanity.com/paper/1705.10220/) (2017)
- [Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions](https://mlsanity.com/paper/1802.06310/) (2018)
- [Permutation-Based Causal Structure Learning with Unknown Intervention Targets](https://mlsanity.com/paper/1910.09007/) (2019)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [Budgeted Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1709.03625/) (2017)
- [Active Invariant Causal Prediction: Experiment Selection through Stability](https://mlsanity.com/paper/2006.05690/) (2020)
- [Learning and Testing Causal Models with Interventions](https://mlsanity.com/paper/1805.09697/) (2018)
- [Experimental Design for Cost-Aware Learning of Causal Graphs](https://mlsanity.com/paper/1810.11867/) (2018)
- [LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments](https://mlsanity.com/paper/2006.09670/) (2020)
- [Stochastic Conditional Gradient++](https://mlsanity.com/paper/1902.06992/) (2019)
- [Interventional Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1910.05651/) (2019)

## Built on by (most cited first, 17 of 17)

- [Interventions, Where and How? Experimental Design for Causal Models at Scale](https://mlsanity.com/paper/2203.02016/) (2022)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Active Bayesian Causal Inference](https://mlsanity.com/paper/2206.02063/) (2022)
- [Active Learning for Optimal Intervention Design in Causal Models](https://mlsanity.com/paper/2209.04744/) (2022)
- [Differentiable Multi-Target Causal Bayesian Experimental Design](https://mlsanity.com/paper/2302.10607/) (2023)
- [Finding Counterfactually Optimal Action Sequences in Continuous State Spaces](https://mlsanity.com/paper/2306.03929/) (2023)
- [Amortized Active Causal Induction with Deep Reinforcement Learning](https://mlsanity.com/paper/2405.16718/) (2024)
- [When Selection Meets Intervention: Additional Complexities in Causal Discovery](https://mlsanity.com/paper/2503.07302/) (2025)
- [Neural Design for Genetic Perturbation Experiments](https://mlsanity.com/paper/2207.12805/) (2022)
- [Sequential Underspecified Instrument Selection for Cause-Effect Estimation](https://mlsanity.com/paper/2302.05684/) (2023)
- [Simulation-based Benchmarking for Causal Structure Learning in Gene Perturbation Experiments](https://mlsanity.com/paper/2407.06015/) (2024)
- [No Foundations without Foundations -- Why semi-mechanistic models are essential for regulatory biology](https://mlsanity.com/paper/2501.19178/) (2025)
- [Goal-Oriented Sequential Bayesian Experimental Design for Causal Learning](https://mlsanity.com/paper/2507.07359/) (2025)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [Efficient Data Selection for Training Genomic Perturbation Models](https://mlsanity.com/paper/2503.14571/) (2025)
- [Theoretical Guarantees for Causal Discovery on Large Random Graphs](https://mlsanity.com/paper/2511.02536/) (2025)
- [FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions](https://mlsanity.com/paper/2609.32165/) (2026)

## Abstract (arXiv)

Causal structure learning is a key problem in many domains. Causal structures can be learnt by performing experiments on the system of interest. We address the largely unexplored problem of designing a batch of experiments that each simultaneously intervene on multiple variables. While potentially more informative than the commonly considered single-variable interventions, selecting such interventions is algorithmically much more challenging, due to the doubly-exponential combinatorial search space over sets of composite interventions. In this paper, we develop efficient algorithms for optimizing different objective functions quantifying the informativeness of a budget-constrained batch of experiments. By establishing novel submodularity properties of these objectives, we provide approximation guarantees for our algorithms. Our algorithms empirically perform superior to both random interventions and algorithms that only select single-variable interventions.