Research map / Probabilistic and scientific modeling / Causal discovery
Sample Complexity of Interventional Causal Representation Learning
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.
Establishes the first finite-sample sample-complexity analysis for interventional causal representation learning with soft interventions and linear transformations, giving PAC guarantees for latent graph recovery up to ancestors and latent variable recovery up to parents using an RKHS score estimator.
Problem
Existing identifiability guarantees for interventional causal representation learning hold only in the infinite-sample regime; finite-sample guarantees for recovering latent causal graphs and variables were missing.
Approach
A score-based CRL framework that uses approximate rank and subspace tests on noisy score-difference correlation matrices, with a general consistent score-difference estimator plugged in, yielding finite-sample PAC bounds; instantiated with an RKHS score estimator giving explicit sample complexities.
Key results
- O((log 1/δ)^4) samples suffice for latent graph recovery up to ancestors with probability 1-δ under the RKHS score estimator, with explicit dependence O((n log(n/δ))^4).
- O((1/ϵ log 1/δ)^4) samples suffice for latent variable recovery up to mixing with parents, with MSE at most ϵ^2 with probability 1-δ.
- Simulations show the model constants are independent of observed dimension d and η* decays exponentially with latent dimension n, while graph recovery probability degrades plateau-like at high score MSE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the RKHS-based score estimator | Proposed interventional CRL algorithms · Latent graph recovery | sample complexity: O((log 1 δ )4) | Helped |
| use the RKHS-based score estimator | Proposed interventional CRL algorithms · Latent variables recovery | sample complexity: O(( 1 ϵ log 1 δ )4) | Helped |
| recover latent variables up to mixing with parents rather than ancestors | Proposed interventional CRL method · Latent variables recovery | identifiability | Helped |
| increase score-difference estimation error | Proposed finite-sample CRL algorithms · Latent graph recovery | graph recovery success rate | Hurt |
Surprising findings
- η* decays exponentially with latent dimension n, since it is an order statistic over 2^n subsets.
Limitations
- Results cover only partial identifiability (up to ancestors) and do not give perfect identifiability via hard interventions.
- Analysis restricted to soft interventions and linear transformations from latent to observed space.
- Requires thresholds eta and gamma tied to unknown model constants (eta*, gamma*) that must be estimated.
Experimental setup
Datasets: synthetic linear Gaussian latent causal models
Metrics: graph recovery success rate (1-delta) score difference MSE model constants beta, beta_min, eta*, gamma*
Builds on: score-based CRL framework (Varici et al.) RKHS-based score estimator (Li and Turner) Davis-Kahan sin theta theorem
Closest papers by meaning
- Causal Representation Learning Made Identifiable by Grouping of Observational Variables (ICML 2024 · similarity 0.91)
- Linear Causal Representation Learning from Unknown Multi-node Interventions (NeurIPS 2024 · similarity 0.90)
- Learning Linear Causal Representations from General Environments: Identifiability and Intrinsic Ambiguity (NeurIPS 2024 · similarity 0.90)
- Unifying Causal Representation Learning with the Invariance Principle (ICLR 2025 · similarity 0.89)
- Learning Mixtures of Unknown Causal Interventions (NeurIPS 2024 · similarity 0.89)
- Identifiable Latent Polynomial Causal Models through the Lens of Change (ICLR 2024 · similarity 0.89)
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.