Relaxed Sparsest-Permutation Formulation for Causal Discovery at Scale

• URL: http://arxiv.org/abs/2605.05568v1
• Date: Thu, 07 May 2026 01:20:29 GMT
• Title: Relaxed Sparsest-Permutation Formulation for Causal Discovery at Scale
• Abstract summary: We show that exact Cholesky factorization is unnecessary for structure recovery.<n>We introduce SCOPE, a sparse-Cholesky pipeline that provides a scalable implementation of the relaxed formulation.<n>Experiments on synthetic and real datasets demonstrate that SCOPE matches the MEC recovery accuracy of substantially slower baselines.
• Score: 1.8160945635344523
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the growing availability of large datasets, causal structure learning remains computationally prohibitive at scale. We revisit sparsest-permutation learning for linear structural equation models and show 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, we establish soundness for Markov equivalence class (MEC) recovery under no-cancellation and sparsest Markov representation assumptions, as well as robustness to ordering misspecification. Motivated by these guarantees, we introduce SCOPE, a sparse-Cholesky pipeline that 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 10k variables.

Related papers

• Neural Renormalization Group Flow for Percolation [2.6754482304270018]
  We develop a supervised, scale-shared neural architecture for two-dimensional site percolation.<n>We observe that it is key that the learned latent representation exhibits critical fluctuations and scale-dependent flows consistent with the renormalization-group structure of percolation.
  arXiv  Detail & Related papers  (2026-08-27T07:56:45Z)
• Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes [13.539613784615605]
  We describe a structured POMDP class in which the visible dynamics are RL and every realized visible transition applies a fixed permutation to a hidden mode.<n>We prove that the pair of current observation and stable class forms an exact finite Markov state.<n>Experiments recover an exact compression from raw states to quotient states and achieve perfect paired-order accuracy with three decision-time memory states.
  arXiv  Detail & Related papers  (2026-07-29T17:03:35Z)
• AnchorMoE: Interpretable Time Series Classification via Anchor-Routed MoE [51.994752158953084]
  AnchorMoE is an interpretable-by-construction classification framework.<n>It encodes multi-view representations of local patches and routes them to specialized experts.<n>Experiments on real-world and synthetic benchmarks demonstrate that AnchorMoE achieves highly competitive classification performance.
  arXiv  Detail & Related papers  (2026-06-02T13:30:54Z)
• Clipping Bottleneck: Stabilizing RLVR via Stochastic Recovery of Near-Boundary Signals [83.0127582612634]
  Near-boundary Rescue (NSR) is a minimal, plug-and-play modification that retains out-of-bound tokens to recover lost signals.<n>NSR substantially improves training stability and delivers consistent gains over strong baselines such as DAPO and GSPO.
  arXiv  Detail & Related papers  (2026-05-21T16:45:31Z)
• Scaling Laws from Sequential Feature Recovery: A Solvable Hierarchical Model [23.79711176655533]
  We study a globally high-degree function represented by a combination of latent compositional features whose weights decrease as a power law.<n>We show that a layer-wise spectral algorithm adapted to this structure achieves improved scaling relative to shallow, non-adaptive methods.<n>We prove sharp feature-wise recovery thresholds and show that aggregating these transitions yields an explicit power-law decay of the prediction error.
  arXiv  Detail & Related papers  (2026-05-14T08:37:28Z)
• Importance-Guided Basis Selection for Low-Rank Decomposition of Large Language Models [9.690793619550654]
  We present Basis Selection with Importance (BSI), a principled low-rank compression framework that ranks and prunes bases.<n>We develop an efficient Hessian-diagonal estimator by adapting the Hutchinson randomized-probing method to loss curvature with symmetric parameter perturbations.<n>We provide a comprehensive theoretical analysis, including loss-increase bounds under basis pruning, explicit propagation of Hessian-diagonal estimation error into these bounds, variance characterization tied to the Hessian spectrum, high-probability sample-complexity guarantees for achieving a target estimation accuracy, and guidance on perturbation intensity.
  arXiv  Detail & Related papers  (2026-05-02T22:35:02Z)
• VaSST: Variational Inference for Symbolic Regression using Soft Symbolic Trees [2.6521352889229446]
  We introduce VaSST, a scalable probabilistic framework for symbolic regression based on variational inference.<n>VaSST achieves superior performance in both structural recovery and predictive accuracy compared to state-of-the-art symbolic regression methods.
  arXiv  Detail & Related papers  (2026-02-27T00:07:31Z)
• SIGMA: Scalable Spectral Insights for LLM Collapse [51.863164847253366]
  We introduce SIGMA (Spectral Inequalities for Gram Matrix Analysis), a unified framework for model collapse.<n>By utilizing benchmarks that deriving and deterministic bounds on the matrix's spectrum, SIGMA provides a mathematically grounded metric to track the contraction of the representation space.<n>We demonstrate that SIGMA effectively captures the transition towards states, offering both theoretical insights into the mechanics of collapse.
  arXiv  Detail & Related papers  (2026-01-06T19:47:11Z)
• Learning Causality for Longitudinal Data [1.2691047660244335]
  This thesis develops methods for causal inference and causal representation learning in high-dimensional, time-varying data.<n>The first contribution introduces the Causal Dynamic Variational Autoencoder (CDVAE), a model for estimating Individual Treatment Effects (ITEs)<n>The second contribution proposes an efficient framework for long-term counterfactual regression based on RNNs enhanced with Contrastive Predictive Coding ( CPC) and InfoMax.<n>The third contribution advances CRL by addressing how latent causes manifest in observed variables.
  arXiv  Detail & Related papers  (2025-12-04T16:51:49Z)
• Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
  Cross-modal retrieval relies on well-matched large-scale datasets that are laborious in practice. We introduce a novel noisy correspondence learning framework, namely textbfSelf-textbfReinforcing textbfErrors textbfMitigation (SREM)
  arXiv  Detail & Related papers  (2023-12-27T09:03:43Z)
• Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent [43.097493761380186]
  gradient algorithms are an efficient method of approximately solving linear systems. We show that gradient descent produces accurate predictions, even in cases where it does not converge quickly to the optimum. Experimentally, gradient descent achieves state-of-the-art performance on sufficiently large-scale or ill-conditioned regression tasks.
  arXiv  Detail & Related papers  (2023-06-20T15:07:37Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Dynamic Bayesian Network Auxiliary ABC-SMC for Hybrid Model Bayesian Inference to Accelerate Biomanufacturing Process Mechanism Learning and Robust Control [2.727760379582405]
  We present a knowledge graph hybrid model characterizing complex causal interdependencies of underlying bioprocessing mechanisms. It can faithfully capture the important properties, including nonlinear reactions, partially observed state, and nonstationary dynamics. We derive a posterior distribution model uncertainty, which can facilitate mechanism learning and support robust process control.
  arXiv  Detail & Related papers  (2022-05-05T02:54:21Z)
• Scalable Intervention Target Estimation in Linear Models [52.60799340056917]
  Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class.
  arXiv  Detail & Related papers  (2021-11-15T03:16:56Z)
• Solving Long-tailed Recognition with Deep Realistic Taxonomic Classifier [68.38233199030908]
  Long-tail recognition tackles the natural non-uniformly distributed data in realworld scenarios. While moderns perform well on populated classes, its performance degrades significantly on tail classes. Deep-RTC is proposed as a new solution to the long-tail problem, combining realism with hierarchical predictions.
  arXiv  Detail & Related papers  (2020-07-20T05:57:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.