Non-asymptotic two-sample kernel testing with the spectrally truncated normalized MMD

1. Problem Statement

The paper addresses the kernel-based two-sample testing problem, where the goal is to determine if two independent samples come from the same distribution ($H_0: P_X = P_Y$) or different distributions ($H_1: P_X \neq P_Y$).

• Context: Standard kernel methods embed distributions into a Reproducing Kernel Hilbert Space (RKHS) and use the Maximum Mean Discrepancy (MMD) as a test statistic.
• Limitations of Existing Methods:
  • Standard MMD: Relies on asymptotic approximations (infinite weighted sums of chi-squared variables) that depend on unknown population quantities, making direct calibration difficult. Practical implementations often require data splitting to estimate quantiles, reducing statistical power.
  • Normalized MMD (nMMD): Recent work introduced a normalized version (analogous to Hotelling's $T^2$) that accounts for within-group data variability via the inverse of the covariance operator. This improves power but requires regularization (typically ridge regularization).
  • The Gap: While ridge-regularized nMMD has asymptotic guarantees, its non-asymptotic null distribution is complex (involving unknown weights), often necessitating data splitting. Furthermore, the standard asymptotic $\chi^2$ approximation for spectrally truncated versions (which use a finite number of eigen-directions) is known to be poorly calibrated for small-to-moderate sample sizes.

2. Methodology: Spectrally Truncated Normalized MMD (st-nMMD)

The authors propose a new testing procedure based on a spectrally truncated version of the normalized MMD, avoiding ridge regularization in favor of truncation.

A. The Test Statistic

Let $\hat{\mu}_X, \hat{\mu}_Y$ be empirical mean embeddings and $\hat{\Sigma}$ be the empirical within-group covariance operator in the RKHS. The authors define the st-nMMD statistic ($\hat{D}^2_T$) as:
$$\hat{D}^2_T = \frac{n_X n_Y}{n_X + n_Y} \sum_{t=1}^T \frac{\langle \hat{f}_t, \hat{\mu}_X - \hat{\mu}_Y \rangle_H^2}{\hat{\lambda}_t}$$
Where:

• $T$ is the truncation level (number of spectral components).
• $\hat{\lambda}_t$ and $\hat{f}_t$ are the empirical eigenvalues and eigenvectors of $\hat{\Sigma}$.
• The sum is restricted to the first $T$ directions where eigenvalues are positive.

This formulation effectively normalizes the difference in mean embeddings by the data variability along specific discriminant directions.

B. Theoretical Framework

The core contribution is a non-asymptotic analysis of $\hat{D}^2_T$ under the null hypothesis.

1. Concentration Inequalities: The authors derive exponential upper bounds for the tail probability of $\hat{D}^2_T$. They utilize self-normalized processes and Hoeffding-type inequalities (adapted from Bertail et al., 2008) combined with operator perturbation theory.
2. Key Assumptions:
   • Balanced sample sizes ($n_X = n_Y = n$).
   • Bounded kernel ($M_k < \infty$).
   • Simple eigenvalues with strictly positive spectral gaps ($\Delta_t$) to ensure stable eigenvector estimation.
3. Quantile Derivation: They derive an explicit, sharp upper bound $Q$ for the $(1-\alpha)$-quantile of the null distribution. This bound depends on the sample size $n$, kernel bound $M_k$, eigenvalues $\lambda_{1:T}$, and spectral gaps $\Delta_{1:T}$.

C. Data-Driven Calibration Algorithm

To make the method practical without data splitting, the authors propose a fully data-driven algorithm:

1. Simplified Quantile: They approximate the complex theoretical bound $Q$ by retaining dominant terms, resulting in a form proportional to the asymptotic $\chi^2(T)$ quantile but scaled by a factor dependent on the signal-to-noise ratio of the eigenvalues.
2. Hyperparameter Tuning:
   • $\rho$ (Scaling Factor): Calibrated directly on the data to ensure the quantile is an upward adjustment of the $\chi^2$ quantile, preventing underestimation of the threshold.
   • $T$ (Truncation Level): Selected automatically using a rule of thumb that retains only eigen-directions where the estimated eigenvalue and spectral gap exceed a noise threshold ($\sim 1/\sqrt{n}$).
3. No Data Splitting: The entire procedure uses the full dataset for both estimation and calibration, preserving statistical power.

3. Key Contributions

1. Non-Asymptotic Theory: The first derivation of an explicit, sharp exponential upper bound for the spectrally truncated normalized MMD under the null hypothesis. This provides rigorous finite-sample guarantees.
2. Optimality Analysis: Demonstration that the proposed quantile is optimal up to a multiplicative factor in the asymptotic regime, aligning with the known $\chi^2(T)$ convergence while correcting for finite-sample bias.
3. Data-Adaptive Procedure: Development of a fully data-driven algorithm that:
   • Estimates the non-asymptotic quantile without data splitting.
   • Automatically selects the optimal truncation parameter $T$.
   • Adapts to the underlying covariance structure (unlike deterministic $\chi^2$ thresholds).
4. Computational Efficiency: By using spectral truncation instead of ridge regularization, the method avoids the computational cost of inverting large matrices or computing full spectral decompositions for every permutation, while still capturing the necessary discriminant directions.

4. Results

The authors validated their method through extensive numerical experiments on synthetic data (Gaussian, Uniform, Cauchy, von Mises-Fisher) and the MNIST dataset.

• Calibration (Type-I Error Control):
  • The proposed st-nMMD test maintains the nominal significance level (e.g., $\alpha=0.05$) across various sample sizes ($n=100$ to $5000$) and dimensions ($d=2$ to $100$).
  • In contrast, the standard asymptotic $\chi^2$ approximation is miscalibrated for small $n$ and low dimensions, often exhibiting inflated Type-I errors (false positives).
• Power Performance:
  • The method is slightly conservative under the null (a trade-off for strict calibration) but maintains competitive empirical power under the alternative hypothesis.
  • As sample size increases, the power of the st-nMMD converges to that of the asymptotic $\chi^2$ test.
  • The data-adaptive nature of the quantile allows the test to adjust to different covariance structures, preventing power loss even when the test is conservative under $H_0$.
• Truncation Selection: The automatic selection of $T$ consistently chooses small values (typically $T < 10$) even in high dimensions, filtering out noise and focusing on informative directions.

5. Significance

This work bridges the gap between theoretical rigor and practical applicability in kernel two-sample testing.

• Theoretical Impact: It resolves the lack of non-asymptotic guarantees for normalized MMD variants, providing a framework that does not rely on asymptotic approximations which fail in finite samples.
• Practical Impact: The proposed algorithm eliminates the need for data splitting, a common practice that halves the effective sample size and reduces test power. By being fully data-adaptive and computationally efficient, it offers a robust solution for high-dimensional statistical testing in fields like genomics, neuroscience, and image analysis (e.g., MNIST).
• Interpretability: The spectral truncation approach inherently provides a "discriminant direction" view, offering insights into how distributions differ (via the selected eigenvectors), unlike binary decision-only tests.

In summary, the paper introduces st-nMMD, a theoretically grounded, data-adaptive, and computationally efficient two-sample test that ensures valid finite-sample calibration without sacrificing statistical power or requiring data splitting.