Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set

Davin Choo, Chandler Squires, Arnab Bhattacharyya, David Sontag
Proceedings of the Fourth Conference on Causal Learning and Reasoning, PMLR 275:1032-1085, 2025.

Abstract

Accurate estimates of causal effects play a key role in decision-making across applications such as healthcare, economics, and operations. In the absence of randomized experiments, a common approach to estimating causal effects uses covariate adjustment. In this paper, we study covariate adjustment for discrete distributions from the PAC learning perspective, assuming knowledge of a valid adjustment set $\mathbf{Z}$, which might be high-dimensional. Our first main result PAC-bounds the estimation error of covariate adjustment by a term that is exponential in the size of the adjustment set; it is known that such a dependency is unavoidable even if one only aims to minimize the mean squared error. Motivated by this result, we introduce the notion of an $\varepsilon$-Markov blanket, give bounds on the misspecification error of using such a set for covariate adjustment, and provide an algorithm for $\varepsilon$-Markov blanket discovery; our second main result upper bounds the sample complexity of this algorithm. Furthermore, we provide a misspecification error bound and a constraint-based algorithm that allow us to go beyond $\varepsilon$-Markov blankets to even smaller adjustment sets. Our third main result upper bounds the sample complexity of this algorithm, and our final result combines the first three into an overall PAC bound. Altogether, our results highlight that one does not need to perfectly recover causal structure in order to ensure accurate estimates of causal effects.

Cite this Paper

BibTeX
@InProceedings{pmlr-v275-choo25a, title = {Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set}, author = {Choo, Davin and Squires, Chandler and Bhattacharyya, Arnab and Sontag, David}, booktitle = {Proceedings of the Fourth Conference on Causal Learning and Reasoning}, pages = {1032--1085}, year = {2025}, editor = {Huang, Biwei and Drton, Mathias}, volume = {275}, series = {Proceedings of Machine Learning Research}, month = {07--09 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v275/main/assets/choo25a/choo25a.pdf}, url = {https://proceedings.mlr.press/v275/choo25a.html}, abstract = {Accurate estimates of causal effects play a key role in decision-making across applications such as healthcare, economics, and operations. In the absence of randomized experiments, a common approach to estimating causal effects uses covariate adjustment. In this paper, we study covariate adjustment for discrete distributions from the PAC learning perspective, assuming knowledge of a valid adjustment set $\mathbf{Z}$, which might be high-dimensional. Our first main result PAC-bounds the estimation error of covariate adjustment by a term that is exponential in the size of the adjustment set; it is known that such a dependency is unavoidable even if one only aims to minimize the mean squared error. Motivated by this result, we introduce the notion of an $\varepsilon$-Markov blanket, give bounds on the misspecification error of using such a set for covariate adjustment, and provide an algorithm for $\varepsilon$-Markov blanket discovery; our second main result upper bounds the sample complexity of this algorithm. Furthermore, we provide a misspecification error bound and a constraint-based algorithm that allow us to go beyond $\varepsilon$-Markov blankets to even smaller adjustment sets. Our third main result upper bounds the sample complexity of this algorithm, and our final result combines the first three into an overall PAC bound. Altogether, our results highlight that one does not need to perfectly recover causal structure in order to ensure accurate estimates of causal effects.} }
Endnote
%0 Conference Paper %T Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set %A Davin Choo %A Chandler Squires %A Arnab Bhattacharyya %A David Sontag %B Proceedings of the Fourth Conference on Causal Learning and Reasoning %C Proceedings of Machine Learning Research %D 2025 %E Biwei Huang %E Mathias Drton %F pmlr-v275-choo25a %I PMLR %P 1032--1085 %U https://proceedings.mlr.press/v275/choo25a.html %V 275 %X Accurate estimates of causal effects play a key role in decision-making across applications such as healthcare, economics, and operations. In the absence of randomized experiments, a common approach to estimating causal effects uses covariate adjustment. In this paper, we study covariate adjustment for discrete distributions from the PAC learning perspective, assuming knowledge of a valid adjustment set $\mathbf{Z}$, which might be high-dimensional. Our first main result PAC-bounds the estimation error of covariate adjustment by a term that is exponential in the size of the adjustment set; it is known that such a dependency is unavoidable even if one only aims to minimize the mean squared error. Motivated by this result, we introduce the notion of an $\varepsilon$-Markov blanket, give bounds on the misspecification error of using such a set for covariate adjustment, and provide an algorithm for $\varepsilon$-Markov blanket discovery; our second main result upper bounds the sample complexity of this algorithm. Furthermore, we provide a misspecification error bound and a constraint-based algorithm that allow us to go beyond $\varepsilon$-Markov blankets to even smaller adjustment sets. Our third main result upper bounds the sample complexity of this algorithm, and our final result combines the first three into an overall PAC bound. Altogether, our results highlight that one does not need to perfectly recover causal structure in order to ensure accurate estimates of causal effects.
APA
Choo, D., Squires, C., Bhattacharyya, A. & Sontag, D.. (2025). Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set. Proceedings of the Fourth Conference on Causal Learning and Reasoning, in Proceedings of Machine Learning Research 275:1032-1085 Available from https://proceedings.mlr.press/v275/choo25a.html.

Related Material