On the Number of Conditional Independence Tests in Constraint-based Causal Discovery

• URL: http://arxiv.org/abs/2603.21844v1
• Date: Mon, 23 Mar 2026 11:33:43 GMT
• Title: On the Number of Conditional Independence Tests in Constraint-based Causal Discovery
• Abstract summary: We propose an algorithm that achieves a better complexity of $pmathcalO(s)$ tests.<n>We prove that any constraint-based algorithm must perform at least $2(s)$ conditional independence tests.
• Score: 20.562877135664852
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning causal relations from observational data is a fundamental problem with wide-ranging applications across many fields. Constraint-based methods infer the underlying causal structure by performing conditional independence tests. However, existing algorithms such as the prominent PC algorithm need to perform a large number of independence tests, which in the worst case is exponential in the maximum degree of the causal graph. Despite extensive research, it remains unclear if there exist algorithms with better complexity without additional assumptions. Here, we establish an algorithm that achieves a better complexity of $p^{\mathcal{O}(s)}$ tests, where $p$ is the number of nodes in the graph and $s$ denotes the maximum undirected clique size of the underlying essential graph. Complementing this result, we prove that any constraint-based algorithm must perform at least $2^{Ω(s)}$ conditional independence tests, establishing that our proposed algorithm achieves exponent-optimality up to a logarithmic factor in terms of the number of conditional independence tests needed. Finally, we validate our theoretical findings through simulations, on semi-synthetic gene-expression data, and real-world data, demonstrating the efficiency of our algorithm compared to existing methods in terms of number of conditional independence tests needed.

Related papers

• On the Slow Convergence to Trivial Solutions of Algorithms for Hard Optimization Problems [5.1739750649736305]
  We study the finite-size behavior of some optimization algorithms across easy, intermediate, and hard regimes.<n>In the intermediate regime where instances are already highly constrained, local algorithms achieve solutions substantially better than their predicted performance in the high-constraint-density limit.<n>This gap between finite-regime and behavior has important practical implications.
  arXiv  Detail & Related papers  (2026-08-19T13:40:11Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Membership Testing in Markov Equivalence Classes via Independence Query Oracles [17.84347390320128]
  We show that it is relatively easier to test causal relationships than to learn them. In particular, it requires exponentially less independence tests in graphs featuring high in-degrees and small clique sizes.
  arXiv  Detail & Related papers  (2024-03-09T02:10:08Z)
• Precise Error Rates for Computationally Efficient Testing [67.30044609837749]
  We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity.<n>An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
  arXiv  Detail & Related papers  (2023-11-01T04:41:16Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Characterization and Learning of Causal Graphs with Small Conditioning Sets [6.52423450125622]
  Constraint-based causal discovery algorithms learn part of the causal graph structure by systematically testing conditional independences. We propose a novel representation that allows us to graphically characterize $k$-Markov equivalence between two causal graphs. We conduct synthetic, and semi-synthetic experiments to demonstrate that the $k$-PC algorithm enables more robust causal discovery in the small sample regime.
  arXiv  Detail & Related papers  (2023-01-22T00:24:22Z)
• Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias [27.06618125828978]
  We consider the problem of learning the causal MAG of a system from observational data in the presence of latent variables and selection bias. We propose a novel computationally efficient constraint-based method that is sound and complete. We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world structures.
  arXiv  Detail & Related papers  (2021-10-22T19:49:59Z)
• Multiple imputation and test-wise deletion for causal discovery with incomplete cohort data [0.0]
  Causal discovery algorithms estimate causal graphs from observational data. Until recently, these algorithms have been unable to handle missing values. We investigate two alternative solutions: Test-wise deletion and multiple imputation.
  arXiv  Detail & Related papers  (2021-08-30T15:51:30Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.