Title: Budgeted Experiment Design for Causal Structure Learning,
Abstract: We study the problem of causal structure learning when the experimenter is
limited to perform at most $k$ non-adaptive experiments of size $1$. We
formulate the problem of finding the best intervention target set as an
optimization problem, which aims to maximize the average number of edges whose
directions are resolved. We prove that the corresponding objective function is
submodular and a greedy algorithm suffices to achieve
$(1-\frac{1}{e})$-approximation of the optimal value. We further present an
accelerated variant of the greedy algorithm, which can lead to orders of
magnitude performance speedup. We validate our proposed approach on synthetic
and real graphs. The results show that compared to the purely observational
setting, our algorithm orients the majority of the edges through a considerably
small number of interventions.