Graph-based Complexity for Causal Effect by Empirical Plug-in
This addresses efficiency challenges in causal inference for researchers and practitioners, offering incremental improvements by applying known graph complexity measures to a specific bottleneck.
The paper tackles the computational complexity of estimating causal effects via empirical plug-in methods, showing that evaluation can be efficient, potentially linear in data size, contrary to assumptions of exponential time, with bounds based on treewidth and hypertree width of the estimand's structure.
This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. Given a causal graph and observational data, any identifiable causal query can be estimated from an expression over the observed variables, called the estimand. The estimand can then be evaluated by plugging in probabilities computed empirically from data. In contrast to conventional wisdom, which assumes that high dimensional probabilistic functions will lead to exponential evaluation time of the estimand. We show that computation can be done efficiently, potentially in time linear in the data size, depending on the estimand's hypergraph. In particular, we show that both the treewidth and hypertree width of the estimand's structure bound the evaluation complexity of the plug-in estimands, analogous to their role in the complexity of probabilistic inference in graphical models. Often, the hypertree width provides a more effective bound, since the empirical distributions are sparse.