On the Complexity of Identification in Linear Structural Causal Models
This addresses the fundamental challenge of causal inference in machine learning and statistics, providing both algorithmic improvements and hardness results for researchers in these fields.
The authors tackled the problem of identifying causal parameters in linear structural causal models, presenting a new polynomial-space algorithm that improves the state-of-the-art from double exponential to exponential time, and proved that parameter identification is computationally hard, specifically coNP-hard.
Learning the unknown causal parameters of a linear structural causal model is a fundamental task in causal analysis. The task, known as the problem of identification, asks to estimate the parameters of the model from a combination of assumptions on the graphical structure of the model and observational data, represented as a non-causal covariance matrix. In this paper, we give a new sound and complete algorithm for generic identification which runs in polynomial space. By standard simulation results, this algorithm has exponential running time which vastly improves the state-of-the-art double exponential time method using a Gröbner basis approach. The paper also presents evidence that parameter identification is computationally hard in general. In particular, we prove, that the task asking whether, for a given feasible correlation matrix, there are exactly one or two or more parameter sets explaining the observed matrix, is hard for $\forall R$, the co-class of the existential theory of the reals. In particular, this problem is $coNP$-hard. To our best knowledge, this is the first hardness result for some notion of identifiability.