Technical Summary: A Martingale Kernel Independence Test

1. Problem Statement

The paper addresses the computational and statistical calibration challenges inherent in kernel-based independence testing, specifically the Hilbert–Schmidt Independence Criterion (HSIC) and its extension to joint independence, dHSIC.

Standard implementations of HSIC and dHSIC rely on degenerate V-statistics. Under the null hypothesis of independence ($H_0$), the rescaled statistics converge to a weighted sum of $\chi^2$ random variables, where the weights depend on the unknown joint data distribution. Consequently, practical calibration requires permutation tests to approximate the null distribution. This process involves recomputing the statistic $B$ times (typically $B \ge 200$), inflating the per-test computational cost from $O(n^2)$ to $O(B n^2)$, a factor of two orders of magnitude.

The authors aim to eliminate the permutation step entirely by constructing statistics with a known, distribution-free null limit (standard normal), thereby reducing the per-test cost to match the quadratic complexity of the biased V-statistic itself.

2. Methodology

The proposed approach adapts the recent martingale MMD construction for two-sample testing (Chatterjee and Ramdas [2025]) to the independence setting. The core idea is to transform the standard quadratic-time estimator into a sum of martingale differences, which can then be studentized to converge to a standard normal distribution via the self-normalized martingale Central Limit Theorem (CLT).

2.1 The mHSIC Statistic (Bivariate Independence)

For testing independence between two variables $X$ and $Y$, the authors define mHSIC.

• Construction: The statistic is a studentized, lower-triangular sum of the Hadamard product of two empirically centered Gram matrices ($K_X$ and $K_Y$).
  $$\hat{T}^{\text{mHSIC}}_n = \frac{1}{n} \sum_{i=2}^n \frac{1}{i} \sum_{j=1}^{i-1} (HK_XH)_{ij} (HK_YH)_{ij}$$
• Studentization: The statistic is normalized by its empirical quadratic variation $\hat{\sigma}_n$.
• Theoretical Basis: Under $H_0$, the kernel product $\bar{k}_X \bar{k}_Y$ (where $\bar{k}$ denotes population-centered kernels) forms a martingale difference sequence. Although the empirical centering matrix $H$ introduces a bias, the authors prove this bias is $O_P(1/\sqrt{n})$ and asymptotically negligible after studentization.
• Properties: Under bounded fourth-moment conditions, mHSIC converges to $\mathcal{N}(0, 1)$ regardless of the data law. It is consistent against every fixed alternative and maintains an $O(n^2)$ computational cost without sample splitting.

2.2 The mdHSIC Statistic (Joint Independence)

For testing joint independence among $d$ variables ($X_1, \dots, X_d$), a naive extension of mHSIC fails.

• The Failure of Direct Product: Replacing the bivariate kernel with a $d$-fold product of empirically centered kernels results in an aggregate bias of $O_P(d/\sqrt{n})$. When the number of variables $d$ exceeds $\sqrt{n}$, this bias dominates the studentized scale, breaking the standard normal calibration.
• The Split-Martingale Solution (mdHSIC): To resolve this, the authors introduce a single half-sample split:
  1. Split: The sample is divided into $S_1$ (first half) and $S_2$ (second half).
  2. Centering: The mean embeddings and centered kernels are estimated using only $S_1$.
  3. Martingale Run: The lower-triangular self-normalized martingale sum is computed using the $S_1$-centered kernels applied to pairs within $S_2$.
• Theoretical Basis: This construction ensures the conditional mean residual of the kernel product is $O_P(m^{-d/2})$ (where $m \approx n/2$). This residual is exponentially small in $d$, making it negligible for any fixed $d \ge 2$.
• Properties: mdHSIC converges to $\mathcal{N}(0, 1)$ for any fixed $d$ under joint independence. The per-test cost is $O(d n^2)$, linear in $d$, avoiding the permutation factor $B$.

3. Key Contributions

1. mHSIC: A permutation-free, sample-split-free statistic for bivariate independence that converges to a standard normal distribution under the null, matching the $O(n^2)$ cost of the biased HSIC V-statistic.
2. mdHSIC: A permutation-free statistic for joint independence of $d$ variables. It corrects the empirical centering bias of direct-product extensions via a single half-sample split, ensuring asymptotic normality for any fixed $d$ with $O(d n^2)$ complexity.
3. Theoretical Guarantees: Proofs of convergence to $\mathcal{N}(0, 1)$ under the null (Theorems 3 and 6) and consistency against fixed alternatives, relying on the self-normalized martingale CLT (Fan [2018]).
4. Empirical Validation: Demonstration that both statistics match the Type-I error rates and test power of permutation-calibrated baselines while achieving significant speedups.

4. Experimental Results

The authors evaluated the methods on synthetic data with varying dimensions and sample sizes.

• Calibration (Type-I Error):
  • mHSIC: On bivariate data with ambient dimensions up to 500, the empirical Type-I error rate at $\alpha=0.05$ remained tight around the nominal level for sufficiently large $n$. The authors note a "finite-sample curse of dimensionality" where the error rate inflates if $d_{\text{ambient}} \gtrsim n^{0.875}$ due to residual centering bias.
  • mdHSIC: On joint independence tasks with $d \in \{2, \dots, 10\}$, the Type-I error rate remained within $[0.036, 0.066]$ across all tested sample sizes and dimensions, confirming the distribution-free calibration.
• Power: Both statistics exhibited monotonic power increases with dependence strength and sample size, matching the performance of permutation-based baselines.
• Computational Efficiency:
  • mHSIC and mdHSIC were 25 to 60 times faster than their permutation-calibrated counterparts (HSIC-perm and dHSIC-perm with $B=200$).
  • For $n=16,000$, mHSIC took 0.042 seconds compared to 2.532 seconds for HSIC-perm.
  • The speedup scales with $n$ because the permutation cost grows linearly with $B$, while the martingale cost remains constant per test.

5. Significance and Claims

The paper claims to resolve the calibration bottleneck in kernel independence testing. By leveraging martingale structures, the authors eliminate the need for expensive permutation resampling, reducing the computational burden by two orders of magnitude while preserving statistical validity.

• Permutation-Free: The primary significance is the replacement of the $O(B n^2)$ permutation step with a single normal-quantile lookup, making the tests feasible for large-scale datasets where permutation is prohibitive.
• Robustness: The methods are distribution-free; the null limit is standard normal regardless of the underlying data law, provided mild moment conditions are met.
• Scalability: The mdHSIC statistic specifically addresses the scalability issue in high-dimensional joint independence testing, where naive extensions fail due to compounding bias.

The authors position their work as a direct adaptation of the martingale MMD paradigm (Chatterjee and Ramdas [2025]) to the independence problem, offering a practical alternative to existing sample-splitting methods (like xHSIC) by retaining the lower-triangular structure that utilizes all available pairs in the second half-sample, thereby improving statistical power relative to rectangular cross-block approaches.