New Martingale Kernel Test Runs 60x Faster Without Permutations

A new paper on arXiv proposes a martingale-based approach to kernel independence testing that removes the computationally expensive permutation step. The Hilbert-Schmidt Independence Criterion (HSIC) and its joint-independence extension dHSIC require thousands of permutations to estimate the null distribution, multiplying per-test cost by 50–200×. The authors introduce two new statistics: mHSIC (martingale HSIC) for pairwise independence and mdHSIC (martingale dHSIC) for testing independence across multiple variables simultaneously. Both statistics are studentised and self-normalised so their null distribution is standard normal regardless of the data law—meaning a single normal quantile lookup replaces all permutations. mHSIC uses a lower-triangular sum of the Hadamard product of two centred Gram matrices and runs in O(n²) time without data splitting. mdHSIC employs a half-sample split: centring is estimated on one half and the martingale sum on the other, shrinking the conditional mean residual to an exponentially small quantity, making the test consistent at fixed d with per-test cost linear in d.

The authors validated their method on synthetic data with per-variable input dimensions from 1 to 500 and between 2 and 10 jointly tested variables. Both mHSIC and mdHSIC matched the empirical Type I error rate and test power of permutation-calibrated baselines while running 25 to 60 times faster. This speedup is critical for modern machine learning workflows where independence tests are used repeatedly—for example in causal discovery, feature selection, or testing learned representations. By eliminating the permutation bottleneck, the new statistics make large-scale independence testing practical on datasets that were previously too costly to analyse with existing methods.