Kernel Two-Sample Testing via Directional Components Analysis

Technical Summary: Kernel Two-Sample Testing via Directional Components Analysis

Problem Statement
Standard kernel two-sample tests, particularly those based on the Maximum Mean Discrepancy (MMD), aggregate squared differences across all directions in a Reproducing Kernel Hilbert Space (RKHS). While theoretically sound, these methods suffer in finite-sample regimes, especially in high-dimensional or unbalanced settings. The core issue identified is that the MMD estimator includes "trailing directional components" corresponding to small eigenvalues of the kernel integral operator. In finite samples, these trailing components are estimated with high variance (noise), which degrades the overall test power. Standard permutation-based approaches to determine critical values further exacerbate computational inefficiencies.

Methodology
The authors propose a novel test statistic that leverages the spectral decomposition of the MMD to perform Directional Components Analysis (KDCA). The methodology is built on the observation that estimation quality varies significantly across eigen-directions: leading components (associated with large eigenvalues) are reliably estimated, while trailing components are noisy.

1. Spectral Truncation: Instead of summing over the full RKHS, the proposed method truncates the spectral expansion at a dimension $d$. The test statistic aggregates only the squared norms of the leading $d$ directional components, effectively discarding the noisy tail.
2. Theoretical Foundation: The paper establishes rigorous finite-sample error bounds for the estimation of eigenfunctions and directional components using the kernel's spectral properties. It proves that under the null hypothesis ($H_0: P=Q$), the proposed statistic converges to a weighted sum of independent chi-squared variables.
3. Parametric Bootstrap: To avoid the computational cost of permutation tests, the authors derive the asymptotic null distribution and introduce a computationally efficient parametric bootstrap procedure. This method approximates critical values by resampling from a Gaussian distribution defined by the estimated covariance of the leading directional components.
4. Data-Driven Selection of $d$: A key component is a data-driven algorithm for selecting the truncation dimension $d$. This method maximizes an estimated signal-to-noise ratio (SNR) on a training set, balancing the bias of truncation against the variance of including noisy components.
5. Robustness Analysis: The paper includes a perturbation analysis demonstrating that the test statistic and its limiting distribution are stable with respect to kernel hyperparameter choices, provided a sufficient spectral gap exists between the retained and discarded eigenvalues.

Key Contributions

• Novel Test Statistic: Introduction of a truncated MMD statistic that focuses on well-estimated leading eigen-directions, theoretically justified to improve finite-sample power.
• Asymptotic Theory: Derivation of the asymptotic null distribution (a weighted sum of chi-squared variables) and power analysis under both fixed and local alternatives.
• Efficient Inference: Development of a parametric bootstrap procedure that offers significant speedups over permutation-based alternatives while maintaining valid Type I error control.
• Adaptive Truncation: A principled, data-driven selection criterion for the truncation dimension $d$ that optimizes the SNR without requiring manual tuning or reliance on unstable eigengap estimates.
• Robustness: Formal proof that the method is less sensitive to kernel hyperparameter choices compared to full-rank MMD tests, as the leading spectral components are stable under perturbations.

Results
Extensive simulations and empirical studies validate the method's performance:

• Power: The proposed test (specifically the version with fixed $d=1$, denoted $T_{MMD}(d=1)$) consistently outperforms state-of-the-art kernel tests (including standard MMD, MMD-Agg, SpectraRegu, and others) in high-dimensional and unbalanced settings. It achieves near-perfect power in scenarios where full-rank tests fail due to noise inflation.
• Size Control: The method maintains strict Type I error control across various distributions and dimensions, with rejection rates closely matching the nominal significance level.
• Robustness to Kernel Choice: Unlike standard MMD, which is highly sensitive to bandwidth selection, the truncated method exhibits remarkable stability across different kernel bandwidths.
• Efficiency: The computational cost is significantly lower than permutation-based methods. The proposed method is orders of magnitude faster than full-rank MMD and spectral regularization approaches, making it scalable for large datasets.
• Empirical Application: The method was applied to microarray gene expression datasets (Khan, Gordon, and Chin), where it successfully rejected the null hypothesis with high confidence, often outperforming competing methods in terms of p-values.

Significance and Claims
The paper claims that the inefficiency of standard MMD in finite samples is fundamentally a "variance inflation" problem caused by noisy tail components. By shifting the focus to Directional Components Analysis, the proposed method resolves this by enforcing a hard truncation that retains only the robust, leading eigen-directions.

The authors emphasize that their approach differs fundamentally from spectral regularization methods (e.g., SpectraRegu), which view the problem through the lens of inverse problems and minimax statistics. In contrast, this work views the problem through integral operator learning and dimensionality reduction, prioritizing finite-sample power and computational efficiency. The paper asserts that this targeted aggregation of robust components yields superior power and robustness, particularly in challenging high-dimensional and unbalanced settings, while offering a theoretically justified, fast alternative to permutation testing.