Scalable Computation of Causal Bounds
Madhumitha Shridharan Garud Iyengar
We consider the problem of computing bounds for causal queries on causal
graphs with unobserved confounders and discrete valued observed variables,
where identifiability does not hold. Existing non-parametric approaches for
computing such bounds use linear programming (LP) formulations that quickly
become intractable for existing solvers because the size of the LP grows
exponentially in the number of edges in the causal graph. We show that this LP
can be significantly pruned, allowing us to compute bounds for significantly
larger causal inference problems compared to existing techniques. This pruning
procedure allows us to compute bounds in closed form for a special class of
problems, including a well-studied family of problems where multiple confounded
treatments influence an outcome. We extend our pruning methodology to
fractional LPs which compute bounds for causal queries which incorporate
additional observations about the unit. We show that our methods provide
significant runtime improvement compared to benchmarks in experiments and
extend our results to the finite data setting. For causal inference without
additional observations, we propose an efficient greedy heuristic that produces
high quality bounds, and scales to problems that are several orders of
magnitude larger than those for which the pruned LP can be solved.