On the Complexity of Identification in Linear Structural Causal Models
<|reference_start|>On the Complexity of Identification in Linear Structural Causal Models: 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\"obner 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.<|reference_end|>
@article{dörfler2024on,
    title={On the Complexity of Identification in Linear Structural Causal Models},
    author={Julian D"orfler, Benito van der Zander, Markus Bl"aser, Maciej
  Liskiewicz},
    journal={arXiv preprint arXiv:2407.12528},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.12528},
    primaryClass={cs.AI cs.CC}
}