Optimal Experiments for Partial Causal Effect Identification

• URL: http://arxiv.org/abs/2605.06993v1
• Date: Thu, 07 May 2026 22:16:58 GMT
• Title: Optimal Experiments for Partial Causal Effect Identification
• Abstract summary: We study the problem of selecting, prior to observing experimental outcomes, a cost-constrained subset of experiments that tightens bounds on a target query.<n>We formalize this as the max-potency problem, where maximal potency measures the worst-case reduction in bound width guaranteed by an experiment.<n>We show that ID-pruned experiments are inertly inert, yielding a super-exponential reduction in the number of subsets evaluated.
• Score: 5.4873584968147275
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Causal queries are often only partially identifiable from observational data, and experiments that could tighten the resulting bounds are typically costly. We study the problem of selecting, prior to observing experimental outcomes, a cost-constrained subset of experiments that maximally tightens bounds on a target query. We formalize this as the max-potency problem, where epistemic potency measures the worst-case reduction in bound width guaranteed by an experiment, and show that this problem is NP-hard via a reduction from 0-1 knapsack. Building on the polynomial-programming framework of Duarte et al. (2023), we give a general procedure for evaluating epistemic potency in discrete settings. To control the super-exponential search space, we introduce two graphical pruning criteria that depend only on the causal graph and the query: a novel path-interception rule that exploits district structure to certify zero potency in linear time, and an identifiability check based on the ID algorithm. On Erdos-Renyi random graphs and 11 bnlearn benchmark networks, the two criteria together prune 50-88% of candidate experiments on average without solving a single polynomial program. For the general subset search, we show that ID-pruned experiments are combinatorially inert, yielding a super-exponential reduction in the number of subsets evaluated. We close with an end-to-end demonstration on observational NHANES data, selecting optimal experiments for estimating the effect of physical activity on diabetes.

Related papers

• Decomposing Epistemic Uncertainty for Causal Decision Making [24.553201861455477]
  Causal inference from observational data provides strong evidence for the best action in decision-making without performing expensive randomized trials.<n>Recent work uses neural networks to obtain practical bounds to such causal effects, which is often an intractable problem.<n>We propose a novel framework to address this problem by considering a confidence set around the empirical observational distribution.
  arXiv  Detail & Related papers  (2026-01-30T09:18:11Z)
• Discovering Causal Relationships using Proxy Variables under Unmeasured Confounding [42.70985072862832]
  Inferring causal relationships between variable pairs in the observational study is crucial but challenging.<n>We develop a general nonparametric approach that accommodates both discrete and continuous settings for testing causal hypothesis under unmeasured confounders.<n>We demonstrate the effectiveness of our approach through extensive simulations and real-world data from the Intensive Care Data and World Values Survey.
  arXiv  Detail & Related papers  (2025-10-20T05:13:12Z)
• Design of Experiment for Discovering Directed Mixed Graph [6.3850400710838615]
  We study the problem of experimental design for accurately identifying the causal graph structure of a simple structural causal model (SCM)<n>The presence of cycles renders it impossible to recover the graph skeleton using observational data alone.<n>We develop two classes of algorithms, i.e., bounded and unbounded, that can recover all causal edges except for double adjacent bidirected edges.
  arXiv  Detail & Related papers  (2025-09-02T02:24:55Z)
• A Sample Efficient Conditional Independence Test in the Presence of Discretization [54.047334792855345]
  Conditional Independence (CI) tests directly to discretized data can lead to incorrect conclusions.<n>Recent advancements have sought to infer the correct CI relationship between the latent variables through binarizing observed data.<n>Motivated by this, this paper introduces a sample-efficient CI test that does not rely on the binarization process.
  arXiv  Detail & Related papers  (2025-06-10T12:41:26Z)
• Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes [9.321976218862542]
  In pool-based active learning, the learner is given an unlabeled data set and aims to efficiently learn the unknown hypothesis by querying the labels of the data points. This can be formulated as the classical Optimal Decision Tree (ODT) problem: Given a set of tests, a set of hypotheses, and an outcome for each pair of test and hypothesis, our objective is to find a low-cost testing procedure (i.e., decision tree) that identifies the true hypothesis. In this work, we study a fundamental variant of the ODT problem in which some test outcomes are noisy, even in the more general
  arXiv  Detail & Related papers  (2023-12-23T21:47:50Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Precise Error Rates for Computationally Efficient Testing [67.30044609837749]
  We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity.<n>An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
  arXiv  Detail & Related papers  (2023-11-01T04:41:16Z)
• Approximating Counterfactual Bounds while Fusing Observational, Biased and Randomised Data Sources [64.96984404868411]
  We address the problem of integrating data from multiple, possibly biased, observational and interventional studies. We show that the likelihood of the available data has no local maxima. We then show how the same approach can address the general case of multiple datasets.
  arXiv  Detail & Related papers  (2023-07-31T11:28:24Z)
• Statistical and Computational Phase Transitions in Group Testing [73.55361918807883]
  We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease. We consider two different simple random procedures for assigning individuals tests.
  arXiv  Detail & Related papers  (2022-06-15T16:38:50Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Multiple imputation and test-wise deletion for causal discovery with incomplete cohort data [0.0]
  Causal discovery algorithms estimate causal graphs from observational data. Until recently, these algorithms have been unable to handle missing values. We investigate two alternative solutions: Test-wise deletion and multiple imputation.
  arXiv  Detail & Related papers  (2021-08-30T15:51:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.