Research map / Learning theory and algorithms / Matrix and tensor methods
On the Complexity of Identification in Linear Structural Causal Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a polynomial-space sound and complete algorithm for generic identification in linear SCMs via existential/universal real theory, and shows numerical identification is coNP-hard-type (∀R-hard) with ∃∀R upper bounds.
Problem
Identification of unknown linear causal parameters in linear structural causal models (SCMs) from covariance data: generic identifiability and numerical identifiability, with their computational complexity.
Approach
Formulate generic identifiability as a sentence in the first-order theory of the reals with quantifier alternations and apply Renegar's/quantifier-elimination results to get a polynomial-space algorithm; reduce complement of promise QUAD (exactly one vs. more solutions) to numerical identifiability to prove ∀R-hardness.
Key results
- Generic identifiability is decidable in PSPACE and lies in both ∀∃R and ∃∀R, a large improvement over the doubly exponential Gröbner basis method.
- Numerical identifiability (exactly one vs. more parameter sets for a feasible covariance matrix) is ∀R-hard, hence coNP-hard, and in promise-∀R, so decidable in polynomial space.
- Feasibility of a covariance matrix in the image of the parametrization is expressible in ∃R.
Surprising findings
- Numerical identifiability is hard for ∀R, the first hardness result for a notion of identifiability.
Limitations
- Algorithm is theoretical and not implemented; practical runtime unknown.
- Complexity of generic identifiability remains open between ∃R/∀R bounds; only upper bounds for generic case.
- Results are for recursive (acyclic) models primarily; cyclic extension is only a note.
Experimental setup
Baselines: Gröbner basis method ACID TreeID
Builds on: Gröbner basis identification instrumental variables Renegar's algorithm Koiran's dimension algorithm ETR-completeness
Closest papers by meaning
- Identification for Tree-Shaped Structural Causal Models in Polynomial Time (AAAI 2024 · similarity 0.93)
- Identifiable Latent Polynomial Causal Models through the Lens of Change (ICLR 2024 · similarity 0.88)
- Strong and Weak Identifiability of Optimization-based Causal Discovery in Non-linear Additive Noise Models (ICML 2025 · similarity 0.88)
- On the Parameter Identifiability of Partially Observed Linear Causal Models (NeurIPS 2024 · similarity 0.87)
- Learning Linear Causal Representations from General Environments: Identifiability and Intrinsic Ambiguity (NeurIPS 2024 · similarity 0.87)
- Identifying General Mechanism Shifts in Linear Causal Representations (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.