BETA This research page is an early version. Explanatory text, figure selection, and presentation are still being revised.

NeurIPS 2024

Fast Proxy Experiment Design for Causal Effect Identification

Sepehr Elahi^* · Sina Akbari^* · Jalal Etesami · Negar Kiyavash · Patrick Thiran

^* Equal contribution.

Advances in Neural Information Processing Systems · 2024

Paper NeurIPS Slides Poster Video

Keywords.

causal identification experiment design proxy interventions optimization

TL;DR.

We revisit minimum-cost proxy experiment design and reformulate the problem as weighted Max-SAT and integer linear programming, producing exact algorithms that are dramatically faster in practice. We also develop a polynomial-time adjustment-set-based heuristic that improves on previous heuristics.

Why this matters.

The work makes exact proxy experiment design far more usable. Instead of solving exponentially many NP-hard subproblems, we exploit mature optimization formulations and obtain speedups of several orders of magnitude while preserving exact optimality.

Abstract

Identifying causal effects is a key problem of interest across many disciplines. The two long-standing approaches to estimate causal effects are observational and experimental (randomized) studies. Observational studies can suffer from unmeasured confounding, which may render the causal effects unidentifiable. On the other hand, direct experiments on the target variable may be too costly or even infeasible to conduct. A middle ground between these two approaches is to estimate the causal effect of interest through proxy experiments, which are conducted on variables with a lower cost to intervene on compared to the main target. In an earlier work, we studied this setting and demonstrated that the problem of designing the optimal (minimum-cost) experiment for causal effect identification is NP-complete and provided a naive algorithm that may require solving exponentially many NP-hard problems as a sub-routine in the worst case. In this work, we provide a few reformulations of the problem that allow for designing significantly more efficient algorithms to solve it as witnessed by our extensive simulations. Additionally, we study the closely-related problem of designing experiments that enable us to identify a given effect through valid adjustments sets.

Main message. The same hard causal-design problem can become dramatically easier in practice when it is formulated in the right optimization language.

The paper at a glance

An informal guide to the problem, the idea, and the main results.

proxy interventions experiment design causal identification efficient optimization

1. The problem

Direct interventions on the most scientifically natural variables may be costly, unethical, or impossible. We therefore need a principled way to identify the target effect using cheaper interventions elsewhere in the system.

2. The key idea

We search over proxy interventions rather than direct ones, and do so with algorithms designed to be fast enough for practical use. The key is to target identifiability while exploiting structure in the design space.

3. New exact formulations

Theory + algorithm

We reformulate minimum-cost intervention design as partially weighted Max-SAT and integer linear programming, with additional formulations through submodular maximization and reinforcement learning. The resulting exact algorithms avoid the super-exponential dependence on the number of districts present in the earlier approach.

4. Adjustment-set proxy design

Theory + algorithm

We formulate minimum-cost experiment design for obtaining a valid adjustment set and derive a polynomial-time heuristic for the broader minimum-cost identification problem. This adjustment-based route is both interpretable and computationally efficient.

5. How it works

Specify the target effect and the intervention costs.
Characterize which proxy interventions are identification-relevant.
Search the resulting design space efficiently.
Return a low-cost intervention plan that identifies the target.

What the experiments show

Main empirical message.

The new exact formulations are dramatically faster than the previous minimal-hedge solver: the ILP implementation is typically one to two orders of magnitude faster, while the Max-SAT implementation is four to five orders of magnitude faster in the single-district experiments. The new polynomial-time heuristic also consistently achieves lower normalized cost than the previous H1 and H2 heuristics.

Where this helps

Good fit

You want identifiability but cannot afford direct interventions on key variables.
You need an algorithmic way to compare many proxy intervention candidates.
You care about the design of practical follow-up experiments rather than identifiability in the abstract.

Keep in mind

The paper offers both exact optimization formulations and a fast heuristic, so the same framework supports different computational budgets.
The ILP formulation is particularly convenient when extra design constraints or domain knowledge need to be incorporated explicitly.

Cite this paper

@inproceedings{elahi2024fast,
  title     = {Fast Proxy Experiment Design for Causal Effect Identification},
  author    = {Sepehr Elahi and Sina Akbari and Jalal Etesami and Negar Kiyavash and Patrick Thiran},
  booktitle = {Advances in Neural Information Processing Systems},
  volume    = {37},
  pages     = {51254--51283},
  year      = {2024},
  url       = {https://proceedings.neurips.cc/paper_files/paper/2024/hash/5bd9fbb3a5a985f80c16ddd0ec1dfc43-Abstract.html}
}