A Martingale Kernel Independence Test
Felix Laumann, Zhaolu Liu, Mauricio Barahona · 2026
Read A Martingale Kernel Independence Test by Felix Laumann, Zhaolu Liu, Mauricio Barahona (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22549.txt.
Introduction
Laumann, Liu and Barahona replace costly permutation checks in independence testing with two martingale tests whose null form is plain standard normal. Their first test, mHSIC, sums a self scaled lower triangle of centred Gram products at the biased HSIC cost, with no sample split. Their second test, mdHSIC, splits the sample in half for finite sample consistency at a cost growing only linearly with variable count. On synthetic data up to 500 dimensions, both match permutation baselines for error and power while running 25 to 60 times faster.
Catalog record
| CREATOR | Felix Laumann, Zhaolu Liu, Mauricio Barahona |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50464 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22549
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Martingale Kernel Independence Test Felix Laumann, Zhaolu Liu, Mauricio Barahona Abstract The Hilbert–Schmidt Independence Criterion (HSIC) and its joint-independence extension d HSIC d\mathrm{HSIC} are degenerate V V -statistics whose data-dependent weighted- χ 2 \chi^{2} null limits force a permutation calibration that multiplies the per-test cost by the number of permutations, in practice two orders of magnitude. Adapting the recent martingale MMD construction for two-sample testing to the (joint) independence problem, we introduce two studentised statistics whose null distributions are standard normal regardless of the data law, so that a single normal-quantile lookup replaces the permutation step entirely. The first, m HSIC m\mathrm{HSIC} , is a self-normalised lower-triangular sum of the Hadamard product of two empirically centred Gram matrices. Under independence and bounded-fourth-moment kernels it converges to a standard normal. It is consistent against every fixed alternative, and runs at quadratic cost in the sample size without any sample split, matching the biased HSIC V V -statistic. The naive direct-product extension to d d variables fails because the empirical-centring bias compounds across the d d factors and breaks finite-sample calibration once the number of variables exceeds the square root of the sample size. Our second statistic, m d HSIC md\mathrm{HSIC} , repairs this with a single half-sample split: the centring is estimated on one half and the lower-triangular self-normalised martingale is run on the other, shrinking the conditional-mean residual to a quantity that is exponentially small in d d , so the statistic is asymptotically standard normal at every fixed number of jointly tested variables, with a per-test cost that grows only linearly in d d . On synthetic data with per-variable input dimension from 1 1 to 500 500 and between 2 2 and 10 10 jointly tested variables, both statistics match the empirical type-I error rate and test power of permutation-calibrated baselines while running 25 25 to 60 × 60\times faster. 1 Introduction The Hilbert–Schmidt Independence Criterion (HSIC) ( 5 ) embeds the joint distribution P_{XY} and the product distribution P_{X}\otimes P_{Y} of two random variables X,Y into a reproducing kernel Hilbert space (RKHS) and returns the squared distance. For characteristic kernels, this distance is zero iff X\mathrel{\perp\!\!\!\perp}Y , so HSIC is a fully non-parametric measure of dependence. Given a paired sample \{(X_{i},Y_{i})\}_{i=1}^{n} of size n and bounded characteristic kernels k_{X},k_{Y} on the marginal sample spaces, write K_{X},K_{Y}\in\mathbb{R}^{n\times n} for the corresponding Gram matrices (K_{X})_{ij}:=k_{X}(X_{i},X_{j}) , (K_{Y})_{ij}:=k_{Y}(Y_{i},Y_{j}) . The standard biased V -statistic for HSIC is then \widehat{\mathrm{HSIC}}_{n}\;=\;\tfrac{1}{n^{2}}\,\tr(K_{X}HK_{Y}H),\qquad H\;:=\;I_{n}-\tfrac{1}{n}\mathbf{1}\mathbf{1}^{\top}, (1) where I_{n} is the n\times n identity matrix and \mathbf{1}\in\mathbb{R}^{n} is the vector of all ones, so that H is the empirical centring matrix. This estimator is degenerate under the null hypothesis H_{0}:X\mathrel{\perp\!\!\!\perp}Y , i.e. the rescaled statistic n\,\widehat{\mathrm{HSIC}}_{n} converges to a weighted sum of \chi^{2} random variables whose weights depend on the unknown joint law ( 5 , Theorem 4.1) . Practical implementations therefore approximate the distribution under the null hypothesis by a permutation test, which requires B recomputations of the statistic and inflates the per-test cost from O(n^{2}) to O(B\,n^{2}) . The same degeneracy is known to arise in the two-sample problem, where the unbiased estimator of the squared maximum mean discrepancy (MMD) between two distributions P,Q has an analogous infinite weighted- \chi^{2} null limit ( 4 ) . 2 recently resolved the calibration step in that setting by observing that a slight modification of the standard quadratic-time estimator \displaystyle T_{n} \displaystyle\;=\;\frac{1}{n}\sum_{i=2}^{n}\frac{1}{i}\sum_{j=1}^{i-1}\Phi^{m\mathrm{MMD}}(Z_{i},Z_{j}), \displaystyle\Phi^{m\mathrm{MMD}}(Z_{i},Z_{j}) \displaystyle\;:=\;k(X_{i},X_{j})-k(X_{i},Y_{j})-k(X_{j},Y_{i})+k(Y_{i},Y_{j}), (2) with Z_{i}:=(X_{i},Y_{i}) , \{X_{i}\}_{i=1}^{n}\sim P , \{Y_{i}\}_{i=1}^{n}\sim Q and a single bounded characteristic kernel k on the common sample space, admits a martingale-difference structure under H_{0}:P=Q . Throughout, write \mathcal{F}_{i-1}:=(Z_{1},\ldots,Z_{i-1}) for the past observations and \mathbb{E}[\,\cdot\,|\,\mathcal{F}_{i-1}] for the corresponding conditional expectation. Each inner sum \frac{1}{i}\sum_{j<i}\Phi^{m\mathrm{MMD}}(Z_{i},Z_{j}) is the RKHS inner product of an empirical witness function determined by \mathcal{F}_{i-1} , \hat{f}_{i}:=\tfrac{1}{i}\sum_{j<i}\bigl[k(X_{j},\cdot)-k(Y_{j},\cdot)\bigr] , with the increment k(X_{i},\cdot)-k(Y_{i},\cdot) at the current sample, which has zero conditional mean under H_{0} . Studentising T_{n} by its own empirical quadratic variation \sigma_{n}^{2}\;:=\;\frac{1}{n^{2}}\sum_{i=2}^{n}\Bigl(\tfrac{1}{i}\sum_{j<i}\Phi^{m\mathrm{MMD}}(Z_{i},Z_{j})\Bigr)^{\!2} gives the self-normalised statistic \eta_{n}:=T_{n}/\sigma_{n} . The self-normalised martingale Central Limit Theorem (CLT) ( 3 ) then yields \eta_{n}\xrightarrow{d}\mathcal{N}(0,1) under H_{0} without any dependence on P , so a single standard-normal quantile replaces the permutation step. The construction recovers the O(n^{2}) cost of the standard estimator and the test is consistent against every fixed P\neq Q . The paper carries out the extension of this paradigm to kernel independence testing. Concretely, we 1. Define the martingale HSIC ( m\mathrm{HSIC} ) statistic, a studentised lower-triangular sum of the Hadamard product of two empirically centred Gram matrices. Under H_{0}:X\mathrel{\perp\!\!\!\perp}Y and the moment conditions of 2 , m\mathrm{HSIC} converges to \mathcal{N}(0,1) (the standard normal distribution) regardless of P_{XY} (Theorem 3 ); under any fixed alternative for which \mathrm{HSIC}(P_{XY})>0 the test is consistent by a calculation parallel to 2 , at a per-test cost of O(n^{2}) , identical to the biased HSIC V -statistic but without the O(B) permutation resampling step. 2. Define the split-martingale d -variable HSIC ( md\mathrm{HSIC} ) statistic, the extension to mutual independence among d random variables. The naive direct-product analogue of m\mathrm{HSIC} has an O_{P}(d/\sqrt{n}) empirical-centring bias that dominates the studentised scale at d\gtrsim\sqrt{n} and breaks finite-sample calibration. We correct this behaviour with a single half-sample split (as in xd\mathrm{HSIC} of 6 ) that replaces the full-sample centring \mu_{k} by the first-half empirical mean embedding \hat{\mu}_{k}^{\mathcal{S}_{1}} , and runs the lower-triangular self-normalised martingale on the second half. Under joint independence and the analogous moment condition, md\mathrm{HSIC} converges to \mathcal{N}(0,1) at every fixed d\geq 2 (Theorem 6 ), at a per-test cost of O(d\,n^{2}) , linear in d . 3. Empirically validate both statistics on synthetic data-generating processes (DGPs). For m\mathrm{HSIC} we assess various per-variable input dimension of X and Y , which we call the ambient dimension d_{\mathrm{ambient}} , to distinguish it from the integer d that elsewhere in the paper counts random variables. For md\mathrm{HSIC} we iterate over d jointly tested variables. We report runtime against the permutation-calibrated HSIC and d\mathrm{HSIC} baselines (Section 6 ). The technical novelty lies in the choice of the bivariate kernel that is substituted into the lower-triangular martingale construction. Three properties of that kernel suffice for the studentised sum to converge to a standard normal under the null: (i) symmetry, so the sum is unbiased for the population functional; (ii) conditional expectation given the past that vanishes at a rate fast enough to be absorbed by the studentisation, making the sum a martingale-difference sequence; (iii) boundedness with finite fourth moment, so the self-normalised martingale CLT of 3 applies. For the two-sample problem, the kernel \Phi^{m\mathrm{MMD}} in ( 2 ) satisfies all three trivially. For independence ( d=2 ), the centred-kernel product \bar{k}_{X}\,\bar{k}_{Y} satisfies (ii) when the centring uses the marginal mean embeddings, and the empirical-to-population gap is O_{P}(1/\sqrt{n}) and asymptotically negligible after studentisation (Lemma 1 ). For joint independence ( d\geq 3 ) the per-variable gap multiplies across the d factors, producing an O_{P}(d/\sqrt{n}) conditional-mean residual that dominates the studentised scale whenever d\gtrsim\sqrt{n} (Section 5.1 ). Our remedy is a single half-sample split, in the spirit of xd\mathrm{HSIC} ( 6 ) : the centring is estimated from the first half and the lower-triangular martingale is run on the second. The conditional-mean residual then collapses