Approximate Kernel-based Conditional Independence Tests for Fast Non-Parametric Causal Discovery

Constraint-based causal discovery (CCD) algorithms require fast and accurate\nconditional independence (CI) testing. The Kernel Conditional Independence Test\n(KCIT) is currently one of the most popular CI tests in the non-parametric\nsetting, but many investigators cannot use KCIT with large datasets because the\ntest scales cubicly with sample size. We therefore devise two relaxations\ncalled the Randomized Conditional Independence Test (RCIT) and the Randomized\nconditional Correlation Test (RCoT) which both approximate KCIT by utilizing\nrandom Fourier features. In practice, both of the proposed tests scale linearly\nwith sample size and return accurate p-values much faster than KCIT in the\nlarge sample size context. CCD algorithms run with RCIT or RCoT also return\ngraphs at least as accurate as the same algorithms run with KCIT but with large\nreductions in run time.\n