跳转至

A scalable Nyström-based kernel two-sample test with permutations

作者: Antoine Chatalic, Marco Letizia, Nicolas Schreuder, Lorenzo Rosasco
来源: Electronic Journal of Statistics
主题: 数理统计 / 假设检验
相关性: 7/10
链接: https://doi.org/10.1214/26-ejs2537

一、领域脉络与小综述

这个方向是什么 非参数两样本检验的核心统计问题是：给定两组样本，判断它们是否来自同一分布 \(P\) 与 \(Q\)，而不对 \(P, Q\) 施加任何参数化假设（如高斯、线性等）。Maximum Mean Discrepancy (MMD) 是该方向当前最主流的检验统计量之一，它将分布差异映射到再生核希尔伯特空间 (RKHS) 中的范数距离。当前该方向的成熟度体现为：MMD 的渐近分布、minimax 最优分离速率、无偏估计量等理论已基本完备；但计算瓶颈（\(O(n^2)\) 复杂度）与有限样本下 permutation 检验的严格 power 保证，仍是尚未完全闭合的缺口。

发展脉络 - 奠基工作：Gretton et al. (2012) 提出了基于 MMD 的两样本检验及其渐近分布理论，确立了 MMD 作为非参数检验标准工具的地位，但留下了计算复杂度 \(O(n^2)\) 与有限样本校准的口子。 - 主要进展（计算加速）：为了突破 \(O(n^2)\) 瓶颈，出现了几条路线：子采样如 subsampling MMD (Zareba et al.)、随机特征如 random Fourier features (Rahimi & Recht, 2007; Zhao & Meng, 2015)、以及线性时间 MMD (Gretton et al., 2012a)。这些方法虽然将计算降至 \(O(n)\) 或 \(O(n \log n)\)，但作者在文中明确指出它们"往往牺牲了统计功效"。 - 主要进展（minimax 理论）：从理论端，Balasubramanian et al. (2021) 与 Reddi et al. (2015) 等工作确立了 MMD 检验在特定核下的 minimax 最优分离速率（\(n^{-1/2}\) 量级），但理论分析多基于渐近正态近似，未覆盖 permutation 检验这种更实用但更难解析的校准方式。 - 当前 frontier 与本文位置：近期的 Nyström MMD 估计 (Chatalic et al., 2022; Rudi et al., 2015) 与 Random Fourier Features MMD (Sriperumbudur et al., 2015) 开始尝试在保持 RKHS 结构的前提下引入低秩近似。本文正是站在这一前沿：将 Nyström 近似从"估计量"推进到"检验统计量 + permutation 校准"的完整闭环，并首次给出匹配 minimax 最优速率的有限样本 power bound。

子线索聚类 被引文献大致落在三条子线索上： 1. MMD 理论与检验设计：聚焦于 MMD 的定义、渐近分布、minimax 速率（Gretton et al. 2012; Balasubramanian et al. 2021; Reddi et al. 2015）。这一簇确立了"什么是好检验"的理论基准。 2. 大规模核方法计算加速：聚焦于 Nyström 方法、随机特征等低秩近似技术（Rudi et al. 2015; Rahimi & Recht 2007; Chatalic et al. 2022）。这一簇提供了"如何算得快"的工具。 3. Permutation 检验与有限样本保证：聚焦于非参数校准与 power 分析（Romano & Wolf 2005; Kim et al. 2022）。这一簇处理"如何在有限样本下严格控制 Type I error 并分析 power"。

这个方向在追问的核心问题 1. 计算-统计权衡：能否在将计算复杂度从 \(O(n^2)\) 降至 \(O(n m)\)（\(m \ll n\)）的同时，不损失统计功效（即保持 minimax 最优分离速率）？ 2. 有限样本下的 Type I error 与 power 控制：渐近正态近似在有限样本下常因分布偏倚而失效；permutation 检验能精确控制 Type I error，但其 power 的有限样本界如何推导？ 3. 分离速率的紧性：在 RKHS 框架下，两样本检验的 minimax 最优分离速率是 \(n^{-1/2}\)（对特征核），计算近似后的检验能否达到同一速率？

⚠️ 作者的 framing - 作者的 framing：作者将缺口 frame 为"现有加速方法（subsampling, random features）牺牲了统计功效，而 Nyström 近似因为保留了核的 RKHS 结构，能在降计算的同时保持功效"，从而使"Nyström MMD + permutation"成为显然的下一步。 - 被淡化或回避的竞争路线：作者对 Random Fourier Features (RFF) 的讨论仅停留在"它不保持 RKHS 结构"的定性判断，未在相同设定下与 RFF MMD 检验做同台理论对比（如 RFF 是否也能在某种设定下达到 \(n^{-1/2}\) 速率）。此外，作者未讨论基于子采样的 U-统计量高阶投影方法（如你熟悉的 higher-order U-statistics 路线），这可能是一条能保持功效且降计算的平行路线。 - 明显该被引却未出现的：基于 higher-order U-statistics / incomplete U-statistics 的两样本检验工作（如 Blom, 1976; Janson, 1984; 近期的 HOIF 路线），这些工作同样在处理 \(O(n^2)\) 计算瓶颈与功效保持，且与本文的 Nyström 子采样在结构上有深层对称性。这是值得研究者去查的方向。

张力 未见明显对立引用。现有文献在"渐近正态近似下的 minimax 速率"上结论一致；本文的张力主要体现在"渐近理论"与"有限样本 permutation 实践"之间的鸿沟——前者好算但有限样本偏，后者难解析但实用，本文试图用 Nyström 桥接二者。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据交代清楚

  • \(P, Q\)：待检验的两个分布（未知），定义在可测空间 \(\mathcal{X}\) 上。这是我们要推断的对象。
  • \(\mathcal{H}, k\)：再生核希尔伯特空间 (RKHS) 及其对应的正定核函数 \(k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}\)。MMD 在此空间中度量 \(P, Q\) 的差异。
  • \(\text{MMD}(P, Q)\)：目标参数 / estimand，定义为 \(\| \mu_P - \mu_Q \|_{\mathcal{H}}\)，其中 \(\mu_P = \mathbb{E}_{X \sim P}[k(X, \cdot)]\) 是核均值嵌入。
  • \(X_1, \dots, X_n\)：来自 \(P\) 的 i.i.d. 随机变量（可观测样本）。
  • \(Y_1, \dots, Y_n\)：来自 \(Q\) 的 i.i.d. 随机变量（可观测样本），假设两组样本量相等为 \(n\)。
  • \(m\)：Nyström 子采样点数（算法参数，\(m \ll n\)），决定计算复杂度。
  • \(I_1, I_2\)：划分 \(\{1, \dots, n\}\) 的随机子集，\(|I_1| = m\)，\(|I_2| = n - m\)。\(I_1\) 用于构造 Nyström 基底，\(I_2\) 用于计算近似统计量。
  • \(\hat{K}_{I_1 I_1}\)：由子样本 \(I_1\) 构成的 \(m \times m\) 核矩阵。
  • \(\hat{\mu}_{P, I_1}, \hat{\mu}_{Q, I_1}\)：基于 \(I_1\) 的 Nyström 核均值嵌入近似估计。
  • \(\text{MMD}^2_{I_1, I_2}(P, Q)\)：本文的核心检验统计量，基于 Nyström 近似与样本划分构造的 MMD 估计量。
  • \(B\)：Permutation 检验的置换次数（算法参数）。
  • \(\alpha\)：检验的显著性水平（如 0.05）。

模型与数据生成机制： 数据生成机制极为简单：\(X_i \sim P\), \(Y_i \sim Q\)，彼此独立。统计模型是 \((P, Q) \in \mathcal{P} \times \mathcal{P}\)，其中 \(\mathcal{P}\) 是 \(\mathcal{X}\) 上的所有 Borel 概率测度集合（非参数模型）。核 \(k\) 视为已知且固定的（如 Gaussian 核），不参与估计。

可观测数据： 研究者实际能观测到的是 \(\{X_i\}_{i=1}^n\) 与 \(\{Y_i\}_{i=1}^n\) 的样本值，以及核函数在任意两点上的取值 \(k(x, y)\)。不可观测的是分布 \(P, Q\) 本身及其核均值嵌入 \(\mu_P, \mu_Q\)，只能通过样本均值去估计。Permutation 检验中，样本的合并与重排是算法操作，不引入新的不可观测量。

第二步：最小内核——最简特例（特征核 + 单次划分）

剥掉一般核的复杂投影与多次划分的方差缩减技巧，支撑整篇论文的最小内核是：在特征核（characteristic kernel，如 Gaussian 核）下，用 \(m\) 个锚点构造 Nyström 近似 MMD，其检验的分离速率仍能达到 \(n^{-1/2}\)，与全量 MMD 一致。

最简特例下的命题退化与直觉： 在全量 MMD 下，标准 U-统计量 \(\text{MMD}^2_u(P, Q) = \frac{1}{n(n-1)} \sum_{i \neq j} h(X_i, Y_j)\) 的方差为 \(O(1/n)\)，因此检测 \(\text{MMD}(P, Q) \geq \Delta\) 的分离速率是 \(\Delta \asymp n^{-1/2}\)（即当 \(\Delta \gg n^{-1/2}\) 时 power 趋于 1）。

在 Nyström 近似下，核心想法是：将 \(n\) 个样本的核矩阵投影到 \(m\) 个锚点生成的子空间上，相当于把 \(O(n^2)\) 的 U-统计量降维为 \(O(nm)\) 的线性统计量与低秩修正的组合。 具体地： 1. 选定 \(m\) 个锚点（子样本 \(I_1\)），计算核矩阵 \(\hat{K}_{I_1 I_1}\) 及其伪逆。 2. 对剩余 \(n-m\) 个样本（\(I_2\)），计算它们到锚点的核向量，通过伪逆投影回 RKHS 子空间。 3. 在此子空间中，MMD 估计量退化为：基于投影后样本均值的欧氏距离。这本质上是一个 \(m\) 维的参数化均值检验，计算复杂度 \(O(nm)\)。

为什么成立（证明直觉）： 关键在于 Nyström 投影虽然丢弃了核矩阵的高频成分（小特征值），但只要核是特征的，且 \(P \neq Q\)，\(\mu_P - \mu_Q\) 的主要信号必然落在核矩阵的大特征值方向上。当 \(m\) 足够大（\(m \gtrsim \sqrt{n}\)，这是本文的一个隐性条件），Nyström 子空间能捕获 \(\mu_P - \mu_Q\) 的绝大部分能量，投影误差被控制。因此，近似统计量的方差仍为 \(O(1/n)\)，偏差为 \(O(1/m)\)，当 \(m \gg \sqrt{n}\) 时偏差可忽略，分离速率保持 \(n^{-1/2}\)。

三、这篇论文做了什么

三句话 ① 研究了非参数两样本检验中 MMD 的 \(O(n^2)\) 计算瓶颈与有限样本 power 保证缺失的问题。 ② 核心方法是引入 Nyström 低秩近似构造 MMD 估计量，并结合 permutation 检验流程进行校准。 ③ 主要结论是给出了该检验在 MMD 范数分离度下的有限样本 power bound，且证明其分离速率达到 \(n^{-1/2}\) 的 minimax 最优速率，计算复杂度降至 \(O(nm)\)。

关键设定与假设 在第二节最小记号基础上，补全完整设定： - Nyström MMD 估计量定义：采用两阶段划分（two-stage split），将样本分为锚点集 \(I_1\)（大小 \(m\)）与计算集 \(I_2\)（大小 \(n-m\)）。近似统计量为：

\[\text{MMD}^2_{I_1, I_2}(P, Q) = \| \hat{\mu}_{P, I_1, I_2} - \hat{\mu}_{Q, I_1, I_2} \|_{\mathcal{H}_{I_1}}^2\]
其中 \(\mathcal{H}_{I_1}\) 是由 \(I_1\) 生成的 Nyström 子空间，\(\hat{\mu}\) 是基于 \(I_2\) 在此子空间上的均值嵌入估计。这种划分避免了 U-统计量的自依赖，使估计量成为线性统计量的组合。 - Permutation 检验流程：合并 \(\{X_i\}\) 与 \(\{Y_i\}\)，进行 \(B\) 次随机置换，每次置换下重新计算 Nyström MMD，得到经验分布，以此构造临界值。 - 核心假设： 1. 核为特征核：确保 \(\text{MMD}(P, Q) = 0 \iff P = Q\)，这是检验一致性的前提。 2. 核有界：\(\sup_{x \in \mathcal{X}} k(x, x) \leq K\)，这是控制方差与 concentration 的标准条件。 3. 子样本量条件：\(m \gtrsim \sqrt{n}\)（隐含在 power bound 的偏差-方差分解中），确保 Nyström 投影偏差不主导方差。 - 与已有文献的对比：相比 Gretton et al. (2012) 的渐近正态校准，本文用 permutation 保证了有限样本 Type I error 的精确控制；相比 subsampling/linear-time MMD，本文通过 Nyström 投影保留了 RKHS 结构，避免了功效的定性损失；相比 Chatalic et al. (2022) 仅分析估计量方差，本文推进到了检验的 power 分析。

主要结果 - 定理 1（有限样本 Power Bound）：在显著性水平 \(\alpha\) 下，若 \(P, Q\) 的分离度满足 \(\text{MMD}(P, Q) \geq C n^{-1/2}\)（\(C\) 为依赖于核与 \(\alpha\) 的常数），则 Nyström MMD permutation 检验的 power 满足：

\[\mathbb{P}(\text{Reject } H_0) \geq 1 - \delta\]
其中 \(\delta\) 随 \(n\) 增大趋于 0。该 bound 的核心结构是偏差-方差分解：偏差来自 Nyström 投影（\(O(1/m)\)），方差来自样本均值波动（\(O(1/n)\)）。当 \(m \gg \sqrt{n}\) 时，偏差被方差吸收，分离速率退化为 \(n^{-1/2}\)。 - 定理 2 / 推论（Minimax 最优速率）：结合 Balasubramanian et al. (2021) 的 minimax 下界，本文的分离速率 \(n^{-1/2}\) 恰好匹配已知下界，证明 Nyström MMD 检验在 minimax 意义上是最优的（无额外计算代价导致的速率损失）。 - 直觉与必要条件：上述结果成立的必要条件是 \(m \gtrsim \sqrt{n}\)。若 \(m\) 过小（如 \(m = \log n\)），投影偏差将主导，分离速率退化为 \(m^{-1/2}\)，此时检验不再是 minimax 最优。这揭示了计算-统计权衡的精确阈值：计算复杂度 \(O(nm)\) 必须至少为 \(O(n^{3/2})\) 才能保住 minimax 功效。

证明路线与技术技巧 - 整体路线： 1. Nyström 投影误差分解：将 \(\text{MMD}^2_{I_1, I_2}\) 分解为真实 MMD 的平方 + 投影偏差 + 采样方差 + 交叉项。 2. 偏差控制：利用 RKHS 投影的性质，证明 Nyström 子空间上的均值嵌入偏差以 \(O(\| \mu_P - \mu_Q \|_{\mathcal{H}} / m)\) 速率衰减（依赖于核矩阵的谱衰减）。 3. 方差控制：由于划分 \(I_1, I_2\) 的引入，\(\text{MMD}^2_{I_1, I_2}\) 在 \(I_2\) 上是线性统计量，其方差以 \(O(1/n)\) 衰减，可用 Bernstein/Hoeffding 型 concentration 直接控制。 4. Permutation 临界值分析：利用 Kim et al. (2022) 的 permutation 检验 concentration 结果，证明置换分布的临界值在 \(H_0\) 下集中在真实分布的临界值附近，从而将 power 分析转化为对统计量在 \(H_1\) 下偏离临界值的控制。 5. 整合：将偏差、方差、临界值波动合并，得到 power \(\geq 1 - \delta\) 的条件，解出分离度 \(\Delta\) 的下界，即为 \(n^{-1/2}\)。 - 关键跳跃点： - 从 U-统计量到线性统计量：全量 MMD 是二阶 U-统计量，方差与 concentration 分析复杂；Nyström + 划分将其降阶为线性统计量，这是证明能走通的核心跳跃。难点在于：降阶后偏差如何控制？作者通过 RKHS 投影的谱分析绕过。 - Permutation 分布的 concentration：Permutation 检验的临界值是随机的（依赖于样本），其 concentration 比渐近正态临界值难得多。作者直接引用了近期文献（Kim et al. 2022）的 permutation concentration bound，这是证明链条中外部依赖最强的一环。 - 技术技巧点名： 1. Nyström 低秩近似 / RKHS 投影：用于将 \(O(n^2)\) 核矩阵投影到 \(O(nm)\) 子空间，控制偏差。 2. 样本划分：用于消除 U-统计量的自依赖，将方差分析降阶。 3. Permutation concentration bounds：用于控制置换分布临界值的随机波动，替代渐近正态近似。 4. Bernstein-type inequality：用于控制线性统计量的尾部概率。

真实例子与应用 - 数据 / 场景：论文包含模拟实验与真实数据实验。真实数据使用了 Higgs 数据集（高能物理，区分信号与背景分布）与 MNIST 数据集（图像，区分不同数字的分布）。 - 如何用上去：将两组数据（如 Higgs 的信号 vs 背景）视为 \(P\) 与 \(Q\)，计算 Nyström MMD 统计量，通过 permutation 校准判断是否能拒绝 \(H_0\)。对比全量 MMD、subsampling MMD、random features MMD 的 power 与计算时间。 - 得到什么结果：在 Higgs 数据集上，Nyström MMD 在 \(m = \sqrt{n}\) 量级下，计算时间比全量 MMD 快数十倍，而 power 几乎无损（与全量 MMD 持平），显著优于 random features MMD（在相同计算预算下 power 更低）。在 MNIST 上，Nyström MMD 同样在计算效率与 power 之间取得了最优权衡。 - 想说明什么：验证理论预测的 \(m \gtrsim \sqrt{n}\) 阈值——在此阈值下，Nyström MMD 确实能保住 minimax 功效且计算可缩放；同时展示 Nyström 相对 random features 的优势（保留 RKHS 结构带来的功效增益）。

🔎 结论是否比证明窄 - 本文的核心 claim 是"Nyström MMD permutation 检验达到 minimax 最优分离速率"，但定理的严格证明依赖于 \(m \gtrsim \sqrt{n}\) 的条件。在 \(m\) 更小的设定下（如 \(m = O(1)\)），结论是否仍成立（或退化到什么速率）未被严格证明，仅在实验中有所展示。 - Permutation concentration 的引用（Kim et al. 2022）本身有较强的矩条件假设，本文是否在所有核设定下都满足这些矩条件，未做逐条核验，属于泛泛 claim 的区域。

四、开放问题（点到为止，扎根具体语句）

  1. Nyström 与 incomplete U-统计量的统一框架：本文的 Nyström + 划分本质上是一种 incomplete U-统计量设计，但未与 higher-order U-statistics / incomplete U-统计量的 minimax 理论对接。要证什么：Nyström 投影的偏差-方差结构与 incomplete U-统计量的高阶投影结构是否等价？扎根点：第二节最小内核中"线性统计量 + 低秩修正"的分解，与 Janson (1984) 的 incomplete U-统计量方差公式。
  2. \(m \gtrsim \sqrt{n}\) 阈值下的统计-计算权衡下界：本文证明了 \(m \gtrsim \sqrt{n}\) 时可达 minimax 最优，但未证明 \(m < \sqrt{n}\) 时速率必然退化。要估什么：在计算预算 \(O(nm)\) 约束下，两样本检验的 minimax 分离速率的下界是什么？扎根点：定理 1 中偏差项 \(O(1/m)\) 的主导条件。
  3. Permutation concentration 的矩条件紧性：本文依赖 Kim et al. (2022) 的 permutation concentration，该结果要求核的有界性或高阶矩。要证什么：在重尾核 / 无界核下，Nyström MMD permutation 检验的 power bound 是否仍成立？扎根点：定理 1 证明中引用 permutation concentration 的那一步。
  4. Random Features vs Nyström 的同台 minimax 对比：作者定性声称 Nyström 优于 RFF，但未在相同 \(m\) 预算下给出 RFF 的 minimax 分离速率。要估什么：RFF MMD 检验在 \(m \gtrsim \sqrt{n}\) 下的分离速率是否也是 \(n^{-1/2}\)？扎根点：Introduction 中"RFF 不保持 RKHS 结构"的判断，缺乏定量速率对比。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论