A1643
Title: Relaxed sparsest-permutation formulation for causal discovery at scale
Authors: Sang-Yun Oh - University of California, Santa Barbara (United States) [presenting]
Gunwoong Park - Seoul National University (Korea, South)
Sunmin Oh - Seoul National University (Korea, South)
Abstract: Despite the growing availability of large datasets, causal structure learning remains computationally prohibitive at scale. Sparsest-permutation learning for linear structural equation models is revisited, revealing that exact Cholesky factorization is unnecessary for structure recovery. This observation motivates a support-level relaxation that searches for sparse triangular factors over a precision-support screening graph. The relaxed formulation can be efficiently evaluated via masked zero-fill incomplete Cholesky factorization, enabling scalable comparison of candidate orderings. At the population level, soundness for Markov equivalence class (MEC) recovery is established under no-cancellation and sparsest Markov representation assumptions, as well as robustness to ordering misspecification. Motivated by these guarantees, SCOPE, a sparse-Cholesky pipeline, provides a scalable implementation of the relaxed formulation. Experiments on synthetic and real datasets demonstrate that SCOPE matches the MEC recovery accuracy of substantially slower baselines while achieving significantly reduced runtime and scaling to $10^4$ variables.
