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

这是一份关于论文《Spectrally truncated normalized MMD: Non-asymptotic two-sample kernel testing with the spectrally truncated normalized MMD》（谱截断归一化 MMD：基于谱截断归一化最大均值差异的非渐近双样本核检验）的详细技术总结。

1. 研究背景与问题 (Problem)

核心问题：
在核方法（Kernel Methods）框架下，如何对两个未知分布进行非参数双样本检验（Two-sample testing）。传统的最大均值差异（Maximum Mean Discrepancy, MMD）检验虽然强大，但在实际应用中面临以下挑战：

1. 校准困难（Calibration Issues）： 传统的 MMD 统计量在零假设下的渐近分布是无限个加权卡方变量的和，权重取决于未知的总体协方差算子。这导致直接计算分位数不可行，通常需要使用数据分割（Data-splitting）或置换检验（Permutation tests）来估计分位数，增加了计算成本或降低了统计功效。
2. 归一化 MMD 的局限性： 为了克服 MMD 对数据变异性不敏感的问题，研究者提出了归一化 MMD（nMMD），即通过组内协方差算子对差异进行缩放（类似于 Hotelling's $T^2$ 检验的核化版本）。然而，现有的归一化方法通常使用岭回归（Ridge regularization）进行正则化，其零分布形式依然复杂（涉及未知权重的无限加权和），在非渐近（有限样本）情况下仍难以精确校准，往往也需要数据分割。
3. 谱截断（Spectral Truncation）的未充分探索： 虽然谱截断作为一种正则化策略曾被提及，但现有工作未充分探索其在非渐近理论下的性质。谱截断利用协方差算子的特征向量构建判别方向，具有直观的解释性，但其在有限样本下的分位数行为尚不明确。

研究目标：
开发一种基于**谱截断归一化 MMD（st-nMMD）**的非渐近双样本检验方法。该方法旨在：

• 提供理论上的精确校准（无需数据分割）。
• 推导非渐近的分位数上界。
• 设计自适应的超参数选择算法。

---

2. 方法论 (Methodology)

2.1 统计量定义 (st-nMMD)

作者定义了一个新的检验统计量 $\hat{D}^2_T$，它是归一化 MMD 的谱截断版本：
$$\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}$$
其中：

• $\hat{\mu}_X, \hat{\mu}_Y$ 是样本在再生核希尔伯特空间（RKHS）中的经验均值嵌入。
• $\hat{\Sigma}$ 是组内经验协方差算子。
• $(\hat{\lambda}_t, \hat{f}_t)$ 是 $\hat{\Sigma}$ 的前 $T$ 个特征值和特征向量。
• $T$ 是截断参数（保留的特征方向数量）。
• 该统计量本质上是均值差异在数据变异方向上的投影，并除以对应的特征值（方差）进行归一化。

2.2 非渐近理论推导

作者利用**自归一化过程（Self-normalized processes）**的集中不等式，推导了 $\hat{D}^2_T$ 在零假设下的非渐近指数上界。

• 关键假设： 样本平衡（$n_X=n_Y$）、核函数有界、特征值简单且谱间隙（Spectral gaps）有下界。
• 主要结果（定理 1）： 证明了存在一个显式的上界 $Q(n, \delta, \dots)$，使得：
  $$P(\hat{D}^2_T > Q) \leq 9T e^{-\delta}$$
  该上界依赖于样本量 $n$、核界 $M_k$、特征值 $\lambda_t$ 和谱间隙 $\Delta_t$。
• 简化与渐近分析： 进一步推导了更简洁的上界形式，并证明了在渐近极限下，该上界与卡方分布 $\chi^2(T)$ 的分位数行为一致，但在有限样本下提供了更紧的界限。

2.3 数据驱动校准算法

为了在实际中应用，作者提出了一个完全数据驱动的算法，无需数据分割：

1. 分位数估计： 使用经验估计的特征值 $\hat{\lambda}_t$ 和谱间隙 $\hat{\Delta}_t$ 替换理论值。
2. 超参数 $\rho$ 的校准： 引入一个调节参数 $\rho$ 来修正卡方分位数，使其适应有限样本的偏差。通过设定 $\rho$ 与噪声水平（$\sqrt{n}\hat{\lambda}_t\hat{\Delta}_t$）成比例，确保估计量收敛到正确的渐近分位数。
3. 截断参数 $T$ 的选择： 提出了一种启发式规则来选择 $T$。规则基于信噪比：仅保留那些特征值和谱间隙显著大于噪声水平（$1/\sqrt{n}$）的方向。
   $$\hat{T} = \max \{ t : \forall s \leq t, \hat{\lambda}_s \geq \frac{\sqrt{\hat{\lambda}_1}}{\sqrt{2n}} \text{ 且 } 2\hat{\Delta}_s \geq \frac{\sqrt{\hat{\Delta}_1}}{\sqrt{n}} \}$$
   如果 $\hat{T}=0$，则不拒绝零假设。

---

3. 主要贡献 (Key Contributions)

1. 非渐近理论保证： 首次为谱截断归一化 MMD（st-nMMD）建立了严格的非渐近指数集中不等式，给出了显式的分位数上界。这解决了归一化 MMD 在有限样本下难以校准的问题。
2. 无需数据分割的校准： 提出了一种完全数据驱动的校准方法，通过自适应调整超参数（$\rho$ 和 $T$），避免了传统方法中因数据分割导致的样本量损失和计算成本增加。
3. 谱截断的优势挖掘： 证明了谱截断不仅是一种正则化手段，还能自然地提取判别方向。该方法在理论上比渐近卡方近似更准确，特别是在小样本和高维场景下。
4. 自适应截断策略： 设计了一个基于信噪比的截断参数选择算法，能够自动根据数据分布和样本量确定保留的特征方向数量，平衡了偏差和方差。

---

4. 实验结果 (Results)

作者在合成数据（高斯、均匀、柯西、von Mises-Fisher 分布）和 MNIST 数据集上进行了广泛的数值实验：

• 校准性能（Calibration）：
  • 在零假设下，提出的非渐近方法（st-nMMD）在所有样本量（$n=100, 1000, 5000$）和维度（$d=2, 10, 100$）下均保持了良好的校准性（Type-I 误差控制在名义水平 $\alpha$ 以下）。
  • 相比之下，基于渐近 $\chi^2$ 分布的方法在小样本（如 $n=100$）和低维情况下表现出严重的校准失效（Type-I 误差膨胀）。
• 功效性能（Power）：
  • 在备择假设下，尽管非渐近方法在零假设下略微保守，但其统计功效（Power）与渐近方法相当，甚至在某些情况下更具竞争力。
  • 随着样本量增加（$n=5000$），两种方法的性能趋于一致，证明了非渐近方法在有限样本下的有效性。
  • 在 MNIST 数据集上，该方法能有效区分不同数字类别的分布差异。
• 截断参数选择：
  • 实验显示，自动选择的 $T$ 值通常较小，且随着维度 $d$ 的增加而减小，这与理论预期一致（高维下高序特征方向的信息量通常被噪声淹没）。
  • 使用自动选择的 $T$ 并未破坏检验的校准性。

---

5. 意义与结论 (Significance)

• 理论突破： 填补了归一化核检验在非渐近理论方面的空白，证明了谱截断正则化在理论上的优越性（相比岭回归，其渐近分布更简单，且非渐近界限更可控）。
• 实践价值： 提供了一种“即插即用”的检验工具。研究者无需进行耗时的置换检验或数据分割，即可在有限样本、高维数据下获得统计上严格校准的检验结果。
• 可解释性： 谱截断方法利用特征向量构建判别方向，不仅给出“是/否”的检验结论，还能揭示区分两个分布的关键特征方向（例如在单细胞数据分析中识别特定的细胞类型），这是传统黑盒核检验所缺乏的。
• 未来方向： 论文指出未来可进一步研究非平衡样本情况下的性质，以及从极小极大（Minimax）角度分析检验功效。

总结： 该论文提出了一种基于谱截断归一化 MMD 的新型双样本检验方法。通过严格的非渐近理论推导和数据驱动的自适应校准算法，该方法克服了传统核检验在有限样本下校准困难和计算昂贵的缺点，为高维非参数统计检验提供了一个既稳健又高效的解决方案。