# PAC-Causal Learnability: From Identification to Finite-Sample Guarantees

arXiv: https://arxiv.org/abs/2507.18903 · HTML: https://mlsanity.com/paper/2507.18903/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 60 references that are in the map.
- First posted on arXiv 25 Jul 2025.

## Builds on (most cited first, 11 of 11)

- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Conformal Inference of Counterfactuals and Individual Treatment Effects](https://mlsanity.com/paper/2006.06138/) (2020)
- [PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees](https://mlsanity.com/paper/2002.05551/) (2020)
- [Generalization Bounds: Perspectives from Information Theory and PAC-Bayes](https://mlsanity.com/paper/2309.04381/) (2023)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Learning and Testing Causal Models with Interventions](https://mlsanity.com/paper/1805.09697/) (2018)
- [Entropic Causal Inference: Identifiability and Finite Sample Results](https://mlsanity.com/paper/2101.03501/) (2021)
- [Revisiting Agnostic PAC Learning](https://mlsanity.com/paper/2407.19777/) (2024)
- [On the Sample Complexity of Causal Discovery and the Value of Domain Expertise](https://mlsanity.com/paper/2102.03274/) (2021)
- [Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set](https://mlsanity.com/paper/2411.08141/) (2024)

## Abstract (arXiv)

Causal identification asks whether a causal target can be recovered from the observational distribution in an idealized infinite-data setting. In practice, only finite samples are available, and identifiability alone does not determine how much data are needed for reliable estimation. We introduce Probably Approximately Correct Causal (PACC) learnability, which formalizes uniform accuracy-confidence guarantees over a causal model class. From a PAC-learning perspective, we ask how many samples are sufficient to estimate a causal target to accuracy ε with probability at least 1-δ. We show that PACC sample complexity is shaped by three recurring factors: causal identification strength, target complexity, and nuisance complexity, and derive a general sufficient bound linking them to finite-sample causal learning. We illustrate the framework through self-controlled case series, instrumental variables, and propensity-score-based estimation, showing how distinct causal methods can be analyzed within a common framework.