Adaptivity Complexity for Causal Graph Discovery
Davin Choo Kirankumar Shiragur
Causal discovery from interventional data is an important problem, where the
task is to design an interventional strategy that learns the hidden ground
truth causal graph $G(V,E)$ on $|V| = n$ nodes while minimizing the number of
performed interventions. Most prior interventional strategies broadly fall into
two categories: non-adaptive and adaptive. Non-adaptive strategies decide on a
single fixed set of interventions to be performed while adaptive strategies can
decide on which nodes to intervene on sequentially based on past interventions.
While adaptive algorithms may use exponentially fewer interventions than their
non-adaptive counterparts, there are practical concerns that constrain the
amount of adaptivity allowed. Motivated by this trade-off, we study the problem
of $r$-adaptivity, where the algorithm designer recovers the causal graph under
a total of $r$ sequential rounds whilst trying to minimize the total number of
interventions. For this problem, we provide a $r$-adaptive algorithm that
achieves $O(\min\{r,\log n\} \cdot n^{1/\min\{r,\log n\}})$ approximation with
respect to the verification number, a well-known lower bound for adaptive
algorithms. Furthermore, for every $r$, we show that our approximation is
tight. Our definition of $r$-adaptivity interpolates nicely between the
non-adaptive ($r=1$) and fully adaptive ($r=n$) settings where our
approximation simplifies to $O(n)$ and $O(\log n)$ respectively, matching the
best-known approximation guarantees for both extremes. Our results also extend
naturally to the bounded size interventions.