CS Paper Radar

The Statistical Cost of Causal Discovery with Feedback

Sunmin Oh, Seungsu Han, Gunwoong Park

cs.LG stat.ML ·submitted 2026-09-28 00:19 UTC · v1

Abstract

What determines the unavoidable sample cost of learning cyclic causal structure? For cyclic linear non-Gaussian models, we study exact condensation recovery from observational data: identifying the strongly connected component (SCC) partition and all edges between components. We establish the first information-theoretic lower bounds on sample complexity for this target. For $p$ variables, maximum SCC size $s_{\max}$, and maximum external-parent count $d_B$, any estimator requires order $s_{\max}\log(ep/s_{\max})+d_B\log(ep/d_B)$ samples in the worst case over a regular model class. These bounds distinguish the costs of SCC membership and external-parent selection. Under principal invertibility and without correlation faithfulness, we establish a population block-exogeneity principle that identifies unknown root SCCs through residual independence and inclusion minimality. A sparse-adjustment characterization shows that small adjustment sets suffice to identify SCCs and their direct external parents, without regressing on all previously recovered variables. These characterizations yield BlockExo, which attains a structurally matching sample bound without knowing $s_{\max}$ or $d_B$ under suitable conditions. Simulations support the structural dependence of our sample bound and demonstrate BlockExo's sample-efficient recovery in comparisons with other methods for cyclic causal discovery.

Closest papers

Nearest neighbours by meaning across the whole index.

Differentiable Structure Learning for Cyclic Linear Gaussian Models with Latent Confounders

cs.LG cs.AI ·2026-09-29 ·Sadegh Khorasani, Ali Najar, Saber Salehkaleybar, Negar Kiyavash
theory similarity 0.70
Abstract · 42 pages, including appendices

We study causal structure learning from observational data in linear Gaussian structural causal models in the presence of directed cycles and an unknown number of exogenous latent confounders, bounded by a given maximum. We derive the covariance of the observed variables and introduce marginal quasi-equivalence, which characterizes when different causal models share a full-dimensional subset of the observational distributions they can generate. We formulate structure learning as minimization of the Gaussian negative log-likelihood with a logarithmically scaled complexity penalty that counts directed edges and latent variables. For a fixed number of observed variables and a fixed upper bound on latent variables, we establish consistency of global score minimizers up to marginal quasi-equivalence under algebraic faithfulness, structural minimality, and model-overlap assumptions. We parameterize the inclusion of directed edges and candidate latent variables using Bernoulli gates, whose continuous probabilities are optimized jointly with the structural coefficients. Averaging the penalized negative log-likelihood over these gates yields an objective with a closed-form differentiable complexity penalty. We prove that this expected objective has the same global infimum as the corresponding discrete structure-learning objective. Experimental results show that our approach achieves lower recovery error than previous methods in several experimental settings.

0.27

Causal Discovery beyond Conditional Independence: Identifiability, Algorithms, and Statistical Inference for Directed Acyclic and Cyclic Graphs

cs.LG stat.MEstat.ML ·2026-10-16 ·Yang Ni
similarity 0.68
Abstract

Learning causal structure from data requires assumptions about mechanisms, noises, observation schemes, and interventions. Historically, causal discovery has relied primarily on conditional independence. This review focuses on modern causal discovery methods that exploit properties of distributions beyond conditional independence. Our organizing principle separates the source of identification from the statistical estimator and its computational implementation. This perspective connects conditional-independence methods with distributional asymmetries, conditional-moment restrictions, and variation across environments or individuals. We examine discovery under latent confounding and feedback, distinguishing causal information about observed variables from reconstruction of latent structure and emphasizing the additional semantics required by cyclic models. We also distinguish population identification, frequentist and Bayesian consistency, uncertainty quantification, and algorithmic guarantees. Throughout, examples show why the same observational distribution can support different conclusions under different model classes. We conclude with guidance for comparing methods at their identifiable targets and a research agenda for uncertainty, heterogeneous populations, non-scalar variables, and the intersection of discrete data, feedback, and hidden confounding.

0.07

Sample Dependence-Aware Blind Source Separation for Linear Causal Discovery

eess.SP ·2026-10-05 ·Cihan Eralp Kumbasar, Emin Erdem Kumbasar, Tulay Adali
similarity 0.67
Abstract · 5 pages, 2 figures. Submitted to the 2027 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

Causal discovery seeks to determine directional relationships among variables in complex systems, yet observational data alone generally do not identify causal direction. Complete identification therefore requires assumptions beyond linearity and acyclicity. A key approach is the Linear Non-Gaussian Acyclic Model (LiNGAM), which formulates linear structural equation model estimation as a blind source separation (BSS) problem. LiNGAM treats disturbances as mutually independent random variables under independent sampling, relying on higher-order statistics (HOS) and non-Gaussianity for identifiability. This restricts identifiability when multiple disturbances are Gaussian and ignores potentially informative temporal dependence. To broaden causal identifiability, we formulate linear acyclic causal discovery with mutually independent disturbance processes and transfer established BSS identification conditions to causal structure recovery. Under this formulation, replacing the mutual information cost with mutual information rate enables identification under a broader class of disturbances, including Gaussian processes with nonproportional covariance functions. Synthetic experiments reveal the limitations of methods relying solely on HOS or sample dependence, while their joint exploitation provides near-perfect causal recovery across the tested disturbance settings. Experiments on real functional magnetic resonance imaging (fMRI) data further demonstrate that jointly exploiting HOS and sample dependence improves the bootstrap stability of estimated ancestral directionality.

0.17

Local Fisher Information Enables Sparse Causal Discovery

cs.LG stat.ML ·2026-10-03 ·Byeongguk Kang, Donghyeon Lee, Euijong Song, Gunwoong Park
theory similarity 0.67
Abstract

Sparse causal discovery calls for methods that exploit graph structure without estimating high-dimensional densities. We introduce Fisher Information Completion Search (FiCS), a source-first algorithm for additive noise models that uses one local Fisher score for both ordering and parent selection. Under regularity and nonconstant-parent conditions, we prove that a node's local Fisher information equals the noise Fisher information exactly when the conditioning set contains all parents, provided that it contains no descendants. This Fisher parent completion identifies the parent set as the unique minimal Fisher completion. With a maximum conditioning set size $q$ at least the maximum indegree $d$, population FiCS queries marginals of at most $q+1$ variables and recovers the true directed acyclic graph under a positive ordering margin. Bounded conditioning also has a population advantage: reducing $q$ toward $d$ cannot decrease, and can strictly increase, the ordering margin. A growing non-Gaussian family separates local Fisher selection from conditional-variance and leaf-first Fisher ordering. For the regularized kernel Stein estimator, we establish high-dimensional DAG consistency under $q\{1+\log(p/q)\}+\log p=o(n)$, uniform Fisher separation, local approximation, and compatible ridge and parent penalty parameters. Experiments show the strongest gains when $n$ is small relative to $p$, quantify the effect of the conditioning size, and demonstrate competitive reference-graph recovery on three real-data benchmarks.

0.31

AdaPS-LiNGAM: Adaptive Predecessor Selection for Linear Non-Gaussian Acyclic Models under Small-Sample Settings

cs.LG stat.ML ·2026-10-07 ·Shun Yanashima, Kentaro Kanamori, Hirofumi Suzuki
similarity 0.66
Abstract

Causal discovery becomes particularly challenging when the available sample size is small relative to the number of variables. This challenge also arises in the linear non-Gaussian acyclic model (LiNGAM), an identifiable framework for causal discovery from observational data. DirectLiNGAM estimates a causal order, which arranges variables so that causes precede their effects, by sequentially identifying an exogenous variable and removing its linear effect from the remaining variables. We establish a structural limitation of this procedure: when the number of variables exceeds the sample size, repeated residualization necessarily becomes degenerate before the full causal order can be determined. Our analysis further reveals that each residual can be reconstructed using only a graph-determined subset of variables already placed earlier in the causal order, termed the active boundary. This result motivates AdaPS-LiNGAM (Adaptive Predecessor Selection LiNGAM), which reconstructs each residual directly from the original observations using an adaptively chosen sparse subset of those earlier variables. The same subset-selection principle is also applied to the final pruning step for edge estimation. Experiments on synthetic data demonstrate that AdaPS-LiNGAM provides accurate causal-structure recovery in sample-limited settings and degrades more gradually as the sample size decreases.

0.15

Causal Discovery Under Hard Selection Bias: A New Robust Score-Matching Approach

cs.LG ·2026-10-13 ·Yiwen Qiu, Francesco Montagna, Shimeng Huang, Francesco Locatello
published similarity 0.64
Abstract · 30 pages, NeurIPS 2026

Selection bias is a difficult yet widespread problem in causal discovery, occurring whenever non-random selection processes lead to data that is not representative of the underlying populations. Due to its practical importance, related works have been proposed to address the problem under local [Versteeg et al., 2022] or interventional settings [Dai et al., 2025a], but general algorithms for observational data remain elusive. In this paper, we focus on truncated data (hard selection), and provide a general result for Additive Noise Models (ANM). We show that score-based methods are a surprisingly suitable candidate due to a special property of the score function ($\nabla \log p(x)$): deterministic truncation preserves both the score of the joint distribution as well as the Jacobian of the score. While established score-matching algorithms still fail in most settings, we actively leverage this observation to propose a new method for causal discovery that is robust under truncated data with ANMs. Overall, our approach offers a general, robust solution that is agnostic to external information about the selection process and still achieves comparable performance to the state-of-the-art approaches when selection is not present.

0.27

Clique Constraints for Exact Causal Structure Learning

cs.LG math.OCstat.ML ·2026-11-09 ·Xiaoyu He, Pavel Rytíř, Petr Ryšavý, Jakub Mareček
theory similarity 0.64
Abstract · 18 pages, 8 figures, 8 tables

Exact score-based causal structure learning supports explicit structural constraints and optimisation certificates, but its branch-and-cut search can be computationally demanding. We augment exact causal structure learning methods with an upper bound on the maximum clique size of the learned undirected skeleton, enforced at integer candidates through lazy cycle and clique constraints. On static linear-Gaussian Erdős-Rényi and scale-free DAGs, we evaluate callback order, alternative clique-cut policies, incumbent repair, fractional separation, and Big-M bounds. We report causal-recovery metrics jointly with optimality gaps, primal and dual bounds, node throughput, MIPSOL events, and callback cost. Two variants receive particular attention: B3 selects the most violated minimal (k+1)-clique inequality at each callback, whereas C3 repairs an infeasible integer candidate by deleting violating edges and refitting affected regression columns using QR-based least squares. The results do not indicate that clique constraints uniformly accelerate optimisation. However, their benefit depends on graph density, sample size, and cut-management policy, while large collections of correlated constraints can reduce node throughput. Tighter valid Big-M bounds reduced the fixed-budget optimality gap in most tested settings, without necessarily changing SHD or F1 at a fixed time limit. These findings characterize the computational trade-offs of clique-constrained exact causal learning, and identify selective separation and incumbent repair as promising directions.

0.17

sHAIL-Causal: A Sequential Staircase Procedure for Invariant Causal Predictor Discovery

cs.LG stat.ML ·2026-10-05 ·Ernest Fokoué
similarity 0.64
Abstract · 17 pages, 2 figures, 2 tables. Introduces the general sHAIL learning framework and its causal specialization

We introduce sHAIL-Causal, the causal specialization of the Saturated Hierarchical Atomic Incremental Learning (sHAIL) paradigm: a sequential staircase procedure that ascends a nested hierarchy of hypothesis classes H_0 < H_1 < ... < H_K once a saturation signal indicates that mastery of the current stage has plateaued. Where general sHAIL leaves the saturation criterion open, sHAIL-Causal instantiates it with a joint criterion of goodness-of-fit saturation and cross-environment invariance, replacing the complexity control of Structural Risk Minimization. We show, theoretically and by simulation, that complexity-only staircases are seduced by confounded predictors that lower empirical risk without reflecting stable causal structure, whereas an invariance-gated staircase provably halts at the true causal predictor set under a per-variable Richness condition. We show that naive greedy search fails to recover the causal set even under Richness, trace the failure to non-monotonicity of the invariance statistic along single-variable paths, and validate a fix combining bounded-exhaustive block-seeding with a calibrated acceptance threshold. We then extend the guarantee to environments arriving sequentially, yielding a confidence guarantee that stays valid at every arrival, which one-shot exhaustive search cannot offer without repeating its full combinatorial search. We close by formalizing the intervention of a wise teacher who lifts a saturated learner off a plateau of boredom.

0.25