Scalable Computation of Causal Bounds
Authors: Madhumitha Shridharan, Garud Iyengar; Journal: 24(237):1−35, 2023.
Abstract
This study focuses on the problem of computing bounds for causal queries on causal graphs with unobserved confounders and discrete-valued observed variables, where identifiability is not applicable. Current non-parametric approaches for computing such bounds use linear programming (LP) formulations, which become computationally infeasible for existing solvers due to the exponential growth in the size of the LP with the number of edges in the causal graph. However, we demonstrate that this LP can be significantly pruned, enabling the computation of bounds for much larger causal inference problems compared to existing techniques. This pruning technique allows us to derive closed-form bounds for a special class of problems, including a well-studied family of problems involving multiple confounded treatments influencing an outcome. Furthermore, we extend our pruning methodology to fractional LPs, which compute bounds for causal queries incorporating additional observations about the unit. Our experimental results indicate that our methods offer significant runtime improvement compared to benchmarks, and we also extend our results to the finite data setting. For causal inference without additional observations, we propose an efficient greedy heuristic that yields high-quality bounds and can handle problems several orders of magnitude larger than those solvable by the pruned LP.
[abs]