In this thesis proposal, we study various problems arising in experimental design from an algorithmic perspective. We focus on two applications of experimental design: causal discovery and group testing.
For causal discovery, we study algorithms for the problem of learning the causal relationships between a set of observed variables, in the presence of latents, while minimizing a suitable cost of interventions on the observed variables. We consider two intervention cost models: an identity cost model where the cost of an intervention is the same, regardless of what variables it is on, i.e., the goal is just to minimize the number of interventions; a linear cost model where the cost of an intervention on a subset of variables has a linear form. For both the cost models, we give combinatorial algorithms with good theoretical guarantees, by identifying new connections between discrete optimization, graph property testing and efficient intervention design.
As part of the future work, we study the following additional models that generalize our previous works. First, we introduce a new Collaborative Causal Discovery problem, through which we model a common scenario in which we have multiple independent entities each with their own causal graph, and our goal is to simultaneously learn all these causal graphs. Secondly, we study the problem of estimating the number of edges in a graph, where access to the graph is via a Bipartite Independent Set (BIS) oracle. The BIS oracle is related to the interventional access model used in our work for (causal) graph discovery, with other applications in group testing and fine-grained complexity. In this setting, we are interested in developing non-adaptive algorithms that lead to efficient implementations in highly parallelized and low-memory streaming settings. Finally, we study the problem of constructing a small subset of the given population, for estimating the average treatment effect (ATE), a causal quantity that measures the effect of administering a particular treatment. Similar to our previous work, using small subsets allows us to minimize the intervention cost.
Advisors: Andrew McGregor and Cameron Musco