CS Paper Radar

MARCEDES: Score-based causal discovery under non-Gaussianity with continuous optimization

Anamitra Chaudhuri, Anirban Bhattacharya, Yang Ni

cs.LG stat.MLstat.COstat.ME ·submitted 2026-09-25 00:30 UTC · v1

Abstract

We consider the problem of learning the underlying causal directed acyclic graph (DAG) structure corresponding to a structural equation model (SEM) with non-Gaussian errors. Motivated by an intentionally misspecified non-Gaussian SEM with all Laplace errors, we first introduce the mean absolute residual risk, defined over the space of all real matrices, and show that, asymptotically, the risk of the true weighted causal DAG matrix is strictly smaller than that of any other matrix. Nevertheless, to enhance generality and account for high-dimensional and finite-sample settings, we further incorporate row-specific sparsity penalties along with a soft DAG constraint to derive a continuous score function over the space of real matrices. Accordingly, we propose a score-based DAG learning method, named MARCEDES, formulated as an unconstrained score minimization problem, which can be efficiently solved using gradient-based optimization techniques, thereby circumventing the challenges associated with constrained optimization. Furthermore, we develop a computational algorithm to handle the non-smoothness of the score objective and to enable optimal tuning of row-specific sparsity penalties under a generalized Bayes framework. Finally, we demonstrate the efficiency and improved performance of the proposed method over existing approaches through an extensive simulation study.

Closest papers

Nearest neighbours by meaning across the whole index.

Nonasymptotic causal structure learning in generalized linear DAGs with continuous optimization

cs.LG stat.MEmath.STstat.ML ·2026-11-08 ·Chang Deng, Inbeom Lee, Bryon Aragam
similarity 0.77
Abstract

We study the problem of learning directed acyclic graphs from observational data in nonlinear models and provide finite-sample, nonasymptotic statistical guarantees in these models. Although widely studied, statistical guarantees for gradient-based methods in nonlinear models are missing from the literature. Under a generalized linear model for each node, we analyze a global nonsmooth objective combining an exact acyclicity constraint with a quasi-minimax concave penalty, which can be optimized via standard gradient-based solvers. We establish finite-sample guarantees under this model, including the most widely used logistic and Poisson models. Experiments corroborate structure recovery accuracy and computational performance, including both standardized data and negative controls as baselines.

0.08

Causal Discovery in Equal Variance Linear Gaussian DAGs via SURE-Tuned Ridge Regression

cs.LG eess.SPstat.ML ·2026-08-17 ·Sambit Mishra, Urbashi Mitra
published similarity 0.75
Abstract · 5 Pages, 3 Figures. Accepted at 60th Asilomar Conference on Signals, Systems, and Computers 2026

Recovering the directed acyclic graph (DAG) of a structural equation model (SEM) from observational data is a central problem in causal discovery. The iterative gradient descent and per-problem hyperparameter tuning of continuous-optimization methods are poorly suited to two practically important regimes: the sample-limited regime, where the number of samples is comparable to or smaller than the number of nodes in the DAG, and the compute-limited regime. This work proposes SURE-Ridge, a non-iterative, closed-form estimator for equal variance linear Gaussian SEM. The method performs parallel node-wise regressions with regularization parameters chosen adaptively by Stein's unbiased risk estimate (SURE), and applies an adaptive thresholding procedure to extract a DAG from the resulting soft adjacency matrix. Numerical results show that SURE-Ridge achieves the lowest structural Hamming distance in the small-sample regime and the lowest run time across all sample sizes tested, compared with NOTEARS, DAGMA, and GBNSL baselines.

0.57

Mapping and Advancing the Scalability-Accuracy Frontier of Nonlinear Causal Discovery

cs.LG cs.AI ·2026-10-02 ·Hendrik Suhr, Sascha Xu, Jilles Vreeken
similarity 0.72
Abstract

Scalable nonlinear causal discovery requires methods that combine flexible mechanism estimators with efficient search over large graph spaces. Several algorithmic families have been proposed to address this challenge, yet their accuracy-runtime trade-offs remain poorly understood. We empirically compare the four major approaches: differentiable structure learning, amortized structure learning, score-matching, and combinatorial search. Our results reveal complementary bottlenecks: differentiable and amortized methods scale well but exhibit an accuracy gap, score-matching methods can be accurate in low dimensions but degrade quickly for increasing feature sizes, and combinatorial methods remain accurate but are slowed by repeated and redundant local scoring. Motivated by this bottleneck, we develop SPADE, a spline-based score-evaluation scheme that compiles sufficient statistics once and reuses them throughout combinatorial search. Under bounded indegree, its Gaussian variant reduces algorithmic complexity from O(nd^3) to O(nd^2+d^3). Empirically, SPADE shifts the observed scalability-accuracy frontier by orders of magnitude: it solves 100-variable problems with 160K samples in seconds and 1600-variable problems with 2.5K samples in minutes, while retaining high structural accuracy across synthetic and real-world benchmarks. These results reveal a substantial shift in the practical scale of combinatorial search and highlight the importance of evaluating scalable causal-discovery methods along the full accuracy-runtime frontier.

0.20

Provable Guarantees and Efficient Learning of Structural Equation Models with Latent Confounders

cs.LG stat.ML ·2026-09-16 ·Weijian Yu, Jean Honorio
similarity 0.70
Abstract

Causal discovery aims to recover causal relationships from observed data. In various fields, exploring causal relationships among variables remains an important topic, but this task becomes challenging due to the existence of latent confounders. Ignoring such confounders can lead to false associations and incorrect edge directions. In this paper, we study the linear structural equation model with latent confounders. We propose an algorithm that iteratively identifies terminal (observed) nodes and reconstructs the directed acyclic graph of the observed variables. To do this, we recover the precision matrix of the observed variables as a sparse plus low-rank matrix: a sparse matrix captures the conditional dependencies among observed variables, while a low-rank matrix captures the combined influence of a few latent confounders. We establish that for $p$ observed variables, $r$ latent confounders and $s$ edges, our procedure correctly identifies the directed causal relationship among observed variables, for $n \gtrsim \max\{s\log p,\ r p\}$ samples. Experimental results validate our theoretical contributions.

0.20

Score-Based Learning of Cluster DAGs from Interventions

cs.LG stat.ML ·2026-10-08 ·Gaetano Tedesco, Alex Markham
theory similarity 0.68
Abstract

Graphical approaches to causal abstraction transform a low-level causal directed acyclic graph (DAG) over many measured variables into a smaller, high-level DAG whose nodes cluster the original variables and whose edges summarize the causal relations between clusters. Such cluster DAGs are easier to interpret, but learning them requires finding the clusters and recovering the edges between them. Madaleno et al. (2026) learn the interventional coarsening (the cluster DAG that merges variables the interventions cannot distinguish) in two constraint-based phases: first the clusters, then the edges. We introduce COARSE, the first score-based method for this task: it keeps the two-phase structure but, under linear Gaussian assumptions, swaps the constraint-based edge phase for a score-based one. We show that the interventions themselves identify a causal order over the clusters, and learning the edges reduces to a single local search per cluster under a cluster-level BIC score. We prove that the procedure runs in polynomial time and, provided the variables affected by each intervention are correctly identified, that it is consistent. On synthetic and real-world interventional data, COARSE matches state-of-the-art edge recovery given enough samples, with an edge phase up to two orders of magnitude faster, including on dense graphs with hundreds of nodes.

0.35

Causal Discovery for Linear Models with Latent Confounding via Multi-domain Identifiable Representation Learning

cs.LG cs.AI ·2026-10-20 ·Danru Xu, Aapo Hyvärinen, Sara Magliacane
similarity 0.68
Abstract · 29 pages, 6 figures

Causal discovery with latent confounding is particularly challenging, but a common setting in real-world data. In this work, we focus on linear causal models with latent confounding, represented by acyclic directed mixed graphs (ADMGs). Existing methods that fully identify ADMGs typically assume non-Gaussianity or graphical constraints, such as bow-freeness. In contrast, we propose Linear ADMG Learning (LinADMG), a framework for learning ADMGs for linear causal models through identifiable representation learning. Rather than relying on non-Gaussianity or bow-freeness, LinADMG leverages multi-domain settings to identify the noise variables. We show that the identifiability of the noise variables is sufficient for recovering all direct causal relations, and that, under an additional latent-confounding no-cancellation condition, LinADMG can identify the whole ADMG. We implement LinADMG with four identifiable representation learning approaches from the literature and validate the methods on simulated and semisynthetic datasets.

0.30

Epidemiological Causal Graph Identification: Challenges, Identifiability and Algorithms

cs.LG stat.MEstat.ML ·2026-09-17 ·Sambit Mishra, Yingying Wang, Christine K. Johnson, Urbashi Mitra
publishedtheory similarity 0.67
Abstract · 5 pages, 2 figures, accepted at the 60th Asilomar Conference on Signals, Systems, and Computers 2026

Causal discovery from observational data is fundamental to statistics and machine learning, yet determining causal direction without interventions necessitates structural assumptions. Existing identifiability research primarily focuses on continuous variables under additive noise models, often neglecting mixed datasets containing ordinal scales, counts, and continuous measurements. This paper investigates causal discovery in Directed Acyclic Graphs (DAGs) where nodes follow either an ordinal distribution (via an ordered logit model) or a regular one-parameter exponential family distribution. We prove that the edge direction between an ordinal and an exponential family node is distributionally identifiable for generic parameter values. Our findings generalize previous Ordinal-Poisson results to the broader exponential family. Computationally, we introduce a score-based exhaustive search and a masked continuous optimization framework using DAGMA for larger graphs. Numerical results validate the theory, recovering edge orientations within a Markov equivalence class that are unidentifiable under classical structural equation models.

0.63

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.67
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