Research map / Probabilistic and scientific modeling / Treatment effects
Fast Proxy Experiment Design for Causal Effect Identification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Reformulates the minimum-cost intervention design for causal effect identification (MCID) as weighted partial MAX-SAT and ILP problems, plus a polynomial-time min-vertex-cut heuristic via generalized adjustment sets, achieving large speedups over the prior exact algorithm.
Problem
Finding the minimum-cost set of proxy interventions that makes an interventional distribution P_X(Y) identifiable from an ADMG; the existing exact algorithm is doubly exponential and the heuristics are weak.
Approach
Encodes hedge-hitting as a 3-SAT formula built from alternating DFS on directed and bidirected edges, yielding a single WPMAX-SAT or ILP instance with quadratic growth in number of districts; additionally, designs interventions that yield valid generalized adjustment sets via a polynomial-time minimum vertex cut.</n>
Key results
- WPMAX-SAT is on average four to five orders of magnitude faster than MHS in the single-district setting and ILP one to two orders of magnitude faster.
- Time of MHS grows exponentially with the number of districts while WPMAX-SAT and ILP grow polynomially.
- The proposed heuristic consistently achieves lower normalized cost than heuristics H1 and H2 across graph sizes from 10 to 200 vertices.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ILP instead of MHS | MCID exact solving · Erdos-Renyi ADMGs, single-district (20–100 vertices) | average runtime: one to two orders of magnitude faster | Helped |
| Use WPMAX-SAT instead of MHS | MCID exact solving · Erdos-Renyi ADMGs, single-district (20–100 vertices) | average runtime: four to five orders of magnitude faster | Helped |
| Use WPMAX-SAT or ILP instead of MHS | MCID exact solving · Erdos-Renyi ADMGs, multiple districts (n=20; 1–9 districts) | average runtime | Helped |
| Use MinCostGenAdjustment instead of H1 and H2 | MCID heuristic solving · Erdos-Renyi ADMGs (10–200 vertices) | normalized cost | Helped |
| Increase graph size from n=40 to n=500 for WPMAX-SAT | WPMAX-SAT runtime comparison with MHS · Erdos-Renyi ADMGs | average runtime: 230 s for both | Mixed |
| Vary the mean of the Poisson distribution used to sample intervention costs | MHS, ILP, and WPMAX-SAT · Erdos-Renyi ADMGs (n=20) | average runtime | No clear effect |
Surprising findings
- Average runtime shows no clear trend with the mean of the Poisson cost distribution.
Limitations
- Exact WPMAX-SAT and ILP remain exponential in worst case since MCID is NP-complete
- Approximation algorithms for MCID left open
Experimental setup
Datasets: randomly generated Erdos-Renyi ADMGs
Benchmarks: random Erdos-Renyi ADMGs
Metrics: average runtime normalized cost relative to optimal
Baselines: Minimal Hedge Solver (MHS) heuristic H1 heuristic H2
Builds on: MCID algorithm (Algorithm 2, minimal hedge solver) hedge hull pruning algorithm general identifiability
Closest papers by meaning
- A Proxy Variable View of Shared Confounding (ICML 2021 · similarity 0.89)
- Automating the Selection of Proxy Variables of Unmeasured Confounders (ICML 2024 · similarity 0.89)
- Causal Effect Identification with a Single Agnostic Proxy (NeurIPS 2026 · similarity 0.89)
- Transferring Causal Effects using Proxies (NeurIPS 2025 · similarity 0.88)
- Data Fusion for Partial Identification of Causal Effects (NeurIPS 2025 · similarity 0.88)
- Minimum Cost Intervention Design for Causal Effect Identification (ICML 2022 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.