A Fast Kernel-based Conditional Independence test with Application to Causal Discovery

• URL: http://arxiv.org/abs/2505.11085v1
• Date: Fri, 16 May 2025 10:14:57 GMT
• Title: A Fast Kernel-based Conditional Independence test with Application to Causal Discovery
• Authors: Oliver Schacht, Biwei Huang,
• Abstract summary: FastKCI is a scalable and parallelizable kernel-based conditional independence test.<n>Experiments on synthetic datasets and benchmarks on real-world production data validate that FastKCI maintains the statistical power of the original KCI test.
• Score: 9.416064439922001
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Kernel-based conditional independence (KCI) testing is a powerful nonparametric method commonly employed in causal discovery tasks. Despite its flexibility and statistical reliability, cubic computational complexity limits its application to large datasets. To address this computational bottleneck, we propose \textit{FastKCI}, a scalable and parallelizable kernel-based conditional independence test that utilizes a mixture-of-experts approach inspired by embarrassingly parallel inference techniques for Gaussian processes. By partitioning the dataset based on a Gaussian mixture model over the conditioning variables, FastKCI conducts local KCI tests in parallel, aggregating the results using an importance-weighted sampling scheme. Experiments on synthetic datasets and benchmarks on real-world production data validate that FastKCI maintains the statistical power of the original KCI test while achieving substantial computational speedups. FastKCI thus represents a practical and efficient solution for conditional independence testing in causal inference on large-scale data.

Related papers

• Fast Flow Matching based Conditional Independence Tests for Causal Discovery [19.33167245211968]
  Constraint-based causal discovery methods require a large number of conditional independence (CI) tests.<n>We propose the Flow Matching-based Conditional Independence Test (FMCIT)<n>The proposed test leverages the high computational efficiency of flow matching and requires the model to be trained only once throughout the entire causal discovery procedure.
  arXiv  Detail & Related papers  (2026-02-09T06:43:23Z)
• Scalable Causal Discovery from Recursive Nonlinear Data via Truncated Basis Function Scores and Tests [7.021824046220355]
  We introduce two basis-expansion tools for scalable causal discovery.<n>First, the Basis Function BIC score uses truncated additive expansions to approximate nonlinear dependencies.<n>Second, the Basis Function Likelihood Ratio Test (BF-LRT) provides an approximate conditional independence test.
  arXiv  Detail & Related papers  (2025-10-05T16:34:54Z)
• Efficient Ensemble Conditional Independence Test Framework for Causal Discovery [46.328102756312724]
  We introduce the Ensemble Conditional Independence Test (E-CIT), a general and plug-and-play framework.<n>E-CIT partitions the data into subsets, applies a given base CIT independently to each subset, and aggregates the resulting p-values.<n>Results demonstrate that E-CIT not only significantly reduces the computational burden of CITs and causal discovery but also achieves competitive performance.
  arXiv  Detail & Related papers  (2025-09-25T11:31:16Z)
• A Sample Efficient Conditional Independence Test in the Presence of Discretization [54.047334792855345]
  Conditional Independence (CI) tests directly to discretized data can lead to incorrect conclusions.<n>Recent advancements have sought to infer the correct CI relationship between the latent variables through binarizing observed data.<n>Motivated by this, this paper introduces a sample-efficient CI test that does not rely on the binarization process.
  arXiv  Detail & Related papers  (2025-06-10T12:41:26Z)
• Amortized Conditional Independence Testing [6.954510776782872]
  ACID is a transformer-based neural network architecture that learns to test for conditional independence.<n>It consistently achieves state-of-the-art performance against existing baselines under multiple metrics.<n>It is able to generalize robustly to unseen sample sizes, dimensionalities, as well as non-linearities with a remarkably low inference time.
  arXiv  Detail & Related papers  (2025-02-28T10:29:56Z)
• An Efficient Permutation-Based Kernel Two-Sample Test [13.229867216847534]
  Two-sample hypothesis testing is a fundamental problem in statistics and machine learning.<n>In this work, we use a Nystr"om approximation of the maximum mean discrepancy (MMD) to design a computationally efficient and practical testing algorithm.
  arXiv  Detail & Related papers  (2025-02-19T09:22:48Z)
• Practical Kernel Tests of Conditional Independence [33.275712245547815]
  SplitKCI is an automated method for bias control for the Kernel-based Conditional Independence test based on data splitting.<n>We show that our approach significantly improves test level control for KCI without sacrificing test power.
  arXiv  Detail & Related papers  (2024-02-20T18:07:59Z)
• Soft Random Sampling: A Theoretical and Empirical Analysis [59.719035355483875]
  Soft random sampling (SRS) is a simple yet effective approach for efficient deep neural networks when dealing with massive data. It selects a uniformly speed at random with replacement from each data set in each epoch. It is shown to be a powerful and competitive strategy with significant and competitive performance on real-world industrial scale.
  arXiv  Detail & Related papers  (2023-11-21T17:03:21Z)
• On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery [21.12645737093305]
  conditional independence testing is an essential step in constraint-based causal discovery algorithms. We design a test for conditional independence based on our estimator, called VM-CI, which achieves optimal parametric rates. We empirically show that VM-CI outperforms other popular CI tests in terms of either time or sample complexity.
  arXiv  Detail & Related papers  (2023-10-20T14:52:25Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  We propose a novel equation discovery method based on Kernel learning and BAyesian Spike-and-Slab priors (KBASS) We use kernel regression to estimate the target function, which is flexible, expressive, and more robust to data sparsity and noises. We develop an expectation-propagation expectation-maximization algorithm for efficient posterior inference and function estimation.
  arXiv  Detail & Related papers  (2023-10-09T03:55:09Z)
• Sequential Kernelized Independence Testing [101.22966794822084]
  We design sequential kernelized independence tests inspired by kernelized dependence measures. We demonstrate the power of our approaches on both simulated and real data.
  arXiv  Detail & Related papers  (2022-12-14T18:08:42Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• FaDIn: Fast Discretized Inference for Hawkes Processes with General Parametric Kernels [82.53569355337586]
  This work offers an efficient solution to temporal point processes inference using general parametric kernels with finite support. The method's effectiveness is evaluated by modeling the occurrence of stimuli-induced patterns from brain signals recorded with magnetoencephalography (MEG) Results show that the proposed approach leads to an improved estimation of pattern latency than the state-of-the-art.
  arXiv  Detail & Related papers  (2022-10-10T12:35:02Z)
• Efficient Aggregated Kernel Tests using Incomplete $U$-statistics [22.251118308736327]
  Three proposed tests aggregate over several kernel bandwidths to detect departures from the null on various scales. We show that our proposed linear-time aggregated tests obtain higher power than current state-of-the-art linear-time kernel tests.
  arXiv  Detail & Related papers  (2022-06-18T12:30:06Z)
• Accelerated Computation of a High Dimensional Kolmogorov-Smirnov Distance [0.0]
  We extend the powerful Kolmogorov-Smirnov two sample test to a high dimensional form. We call our result the d-dimensional Kolmogorov-Smirnov test (ddKS)
  arXiv  Detail & Related papers  (2021-06-25T15:45:18Z)
• Federated Doubly Stochastic Kernel Learning for Vertically Partitioned Data [93.76907759950608]
  We propose a doubly kernel learning algorithm for vertically partitioned data. We show that FDSKL is significantly faster than state-of-the-art federated learning methods when dealing with kernels.
  arXiv  Detail & Related papers  (2020-08-14T05:46:56Z)

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.