Probably Approximately Correct Causal Discovery

• URL: http://arxiv.org/abs/2507.18903v1
• Date: Fri, 25 Jul 2025 02:51:15 GMT
• Title: Probably Approximately Correct Causal Discovery
• Authors: Mian Wei, Somesh Jha, David Page,
• Abstract summary: We propose the Probably Approximately Correct Causal (PACC) Discovery framework.<n>This framework emphasizes both computational and sample efficiency for established causal methods.<n>It can also provide theoretical guarantees for other widely used methods.
• Score: 21.260465708905585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The discovery of causal relationships is a foundational problem in artificial intelligence, statistics, epidemiology, economics, and beyond. While elegant theories exist for accurate causal discovery given infinite data, real-world applications are inherently resource-constrained. Effective methods for inferring causal relationships from observational data must perform well under finite data and time constraints, where "performing well" implies achieving high, though not perfect accuracy. In his seminal paper A Theory of the Learnable, Valiant highlighted the importance of resource constraints in supervised machine learning, introducing the concept of Probably Approximately Correct (PAC) learning as an alternative to exact learning. Inspired by Valiant's work, we propose the Probably Approximately Correct Causal (PACC) Discovery framework, which extends PAC learning principles to the causal field. This framework emphasizes both computational and sample efficiency for established causal methods such as propensity score techniques and instrumental variable approaches. Furthermore, we show that it can also provide theoretical guarantees for other widely used methods, such as the Self-Controlled Case Series (SCCS) method, which had previously lacked such guarantees.

Related papers

• Argumentative Causal Discovery [13.853426822028975]
  Causal discovery amounts to unearthing causal relationships amongst features in data. We deploy assumption-based argumentation (ABA) to learn graphs which reflect causal dependencies in the data. We prove that our method exhibits desirable properties, notably that, under natural conditions, it can retrieve ground-truth causal graphs.
  arXiv  Detail & Related papers  (2024-05-18T10:34:34Z)
• Towards Causal Foundation Model: on Duality between Causal Inference and Attention [18.046388712804042]
  We take a first step towards building causally-aware foundation models for treatment effect estimations. We propose a novel, theoretically justified method called Causal Inference with Attention (CInA)
  arXiv  Detail & Related papers  (2023-10-01T22:28:34Z)
• Advancing Counterfactual Inference through Nonlinear Quantile Regression [77.28323341329461]
  We propose a framework for efficient and effective counterfactual inference implemented with neural networks. The proposed approach enhances the capacity to generalize estimated counterfactual outcomes to unseen data. Empirical results conducted on multiple datasets offer compelling support for our theoretical assertions.
  arXiv  Detail & Related papers  (2023-06-09T08:30:51Z)
• B-Learner: Quasi-Oracle Bounds on Heterogeneous Causal Effects Under Hidden Confounding [51.74479522965712]
  We propose a meta-learner called the B-Learner, which can efficiently learn sharp bounds on the CATE function under limits on hidden confounding. We prove its estimates are valid, sharp, efficient, and have a quasi-oracle property with respect to the constituent estimators under more general conditions than existing methods.
  arXiv  Detail & Related papers  (2023-04-20T18:07:19Z)
• Valid Inference After Causal Discovery [73.87055989355737]
  We develop tools for valid post-causal-discovery inference. We show that a naive combination of causal discovery and subsequent inference algorithms leads to highly inflated miscoverage rates.
  arXiv  Detail & Related papers  (2022-08-11T17:40:45Z)
• A Meta-Reinforcement Learning Algorithm for Causal Discovery [3.4806267677524896]
  Causal structures can enable models to go beyond pure correlation-based inference. Finding causal structures from data poses a significant challenge both in computational effort and accuracy. We develop a meta-reinforcement learning algorithm that performs causal discovery by learning to perform interventions.
  arXiv  Detail & Related papers  (2022-07-18T09:26:07Z)
• Principled Knowledge Extrapolation with GANs [92.62635018136476]
  We study counterfactual synthesis from a new perspective of knowledge extrapolation. We show that an adversarial game with a closed-form discriminator can be used to address the knowledge extrapolation problem. Our method enjoys both elegant theoretical guarantees and superior performance in many scenarios.
  arXiv  Detail & Related papers  (2022-05-21T08:39:42Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)
• Pulling Up by the Causal Bootstraps: Causal Data Augmentation for Pre-training Debiasing [14.4304416146106]
  We study and extend a causal pre-training debiasing technique called causal bootstrapping. We demonstrate that such a causal pre-training technique can significantly outperform existing base practices.
  arXiv  Detail & Related papers  (2021-08-27T21:42:04Z)
• Incorporating Causal Graphical Prior Knowledge into Predictive Modeling via Simple Data Augmentation [92.96204497841032]
  Causal graphs (CGs) are compact representations of the knowledge of the data generating processes behind the data distributions. We propose a model-agnostic data augmentation method that allows us to exploit the prior knowledge of the conditional independence (CI) relations. We experimentally show that the proposed method is effective in improving the prediction accuracy, especially in the small-data regime.
  arXiv  Detail & Related papers  (2021-02-27T06:13:59Z)
• On Computation and Generalization of Generative Adversarial Imitation Learning [134.17122587138897]
  Generative Adversarial Learning (GAIL) is a powerful and practical approach for learning sequential decision-making policies. This paper investigates the theoretical properties of GAIL.
  arXiv  Detail & Related papers  (2020-01-09T00:40:19Z)

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.