Graph-based Complexity for Causal Effect by Empirical Plug-in
Dechter, Rina Raichev, Anna Tian, Jin Ihler, Alexander T.
Dechter, Rina
Raichev, Anna
Tian, Jin
Ihler, Alexander T.
Supervisor
Department
Machine Learning
Embargo End Date
Type
Conference proceeding
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. Given a causal graph and observational data, any identifiable causal query can be estimated from an expression over the observed variables, called the estimand. The estimand can then be evaluated by plugging in probabilities computed empirically from data. In contrast to conventional wisdom which assumes that high dimensional probabilistic functions will lead to exponential evaluation time, we show that estimand evaluation can be done efficiently, potentially in time linear in the data size, depending on the estimand's hypergraph. In particular, we show that both the treewidth and hypertree width of the estimand's structure bound the evaluation complexity, analogous to their role in bounding the complexity of inference in probabilistic graphical models. In settings with high dimensional functions, the hypertree width often provides a more effective bound, since the empirical distributions are sparse.
Citation
R. Dechter, A. K. Raichev, J. Tian, and A. Ihler, “Graph-based Complexity for Causal Effect by Empirical Plug-in,” in Proc. 28th Int. Conf. Artif. Intell. Stat. (AISTATS 2025), vol. 258, Proc. Mach. Learn. Res., Mai Khao, Thailand, May 3–5, 2025, pp. 4798–4806.
Source
Proceedings of Machine Learning Research
Conference
28th International Conference on Artificial Intelligence and Statistics, AISTATS 2025
Keywords
Computational Complexity, Function Evaluation, Undirected Graphs, Causal Graph, Graph Data, Graph-based, High-dimensional, Higher-dimensional, Hypertrees, Observational Data, Plug-in Estimate, Plug-ins, Probabilistic Functions, Graphic Methods
Subjects
Source
28th International Conference on Artificial Intelligence and Statistics, AISTATS 2025
Publisher
ML Research Press