跳转至

Approximating the null distribution of generalized distance covariance

作者: Dominic Edelmann
主题: 数理统计 / 假设检验
相关性: 6/10
链接: https://arxiv.org/abs/2608.23793

一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是：如何高效且精确地计算距离协方差（distance covariance）检验的 p 值。距离协方差是衡量两个随机向量是否独立的一种非参数度量，其样本版本（V-统计量或 U-统计量）在零假设（独立）下的渐近分布是一个加权卡方和，权重由双中心距离矩阵的总体特征值决定。直接使用该渐近分布需要知道总体特征值，而它们通常未知；置换检验虽然精确但计算成本为 \(O(n^2)\) 或更高，且难以估计极小的 p 值。因此，该子方向的核心张力在于：如何用可观测的样本信息（经验谱）来近似这个加权卡方和，使得近似分布既在理论上渐近有效，又在计算上可行（避免 \(O(n^3)\) 的全谱分解）。当前成熟度：已有多种矩匹配近似（Gamma、Pearson III 型等）和保守近似（卡方检验），但尾部精度或计算效率各有缺陷；本文首次为直接经验谱近似提供了完整的理论证明和高效算法。

发展脉络（history）

  • 奠基工作：Székely, Rizzo & Bakirov (2007) [19] 提出距离协方差，证明其渐近分布为加权卡方和，并给出一个简单的渐近检验（SRB）。该检验被后续文献指出过于保守（见本文 Table 1 中 SRB 的因子低至 0.01–0.02）。
  • 推广与统一：Sejdinovic et al. (2013) [16] 和 Bottcher et al. (2017) [2] 将距离协方差推广到一般负型距离，并建立与 RKHS 中 HSIC 的等价性。Edelmann & Goeman (2022) [5] 进一步给出回归视角。这些工作扩大了适用距离类，但未解决零分布近似问题。
  • 矩匹配与保守近似：为避开置换检验，Huang & Huo (2021) [8] 提出 Gamma 近似（匹配前两阶矩）；Berschneider & Bottcher (2018) [1] 提出 BB2（Gamma，匹配前两阶矩的无偏估计）和 BB3（Pearson III 型，匹配前三阶矩）；Shen, Panda & Vogelstein (2022) [17] 提出卡方检验（SPV）。这些方法计算快（\(O(n^2)\) 或 \(O(n \log n)\)），但本文模拟表明：Gamma 在尾部严重 anti-conservative（因子高达 72），SPV 和 BB2 保守，BB3 在中等样本下尚可但尾部仍有偏差（因子 1.3–2.0）。
  • 当前 frontier 与本文位置：直接利用经验谱近似渐近分布的想法在 HSIC 文献中已有使用（Gretton et al. 2009 [7]），但缺乏严格的理论证明。本文首次在可分离度量空间上、对一类连续负型距离，严格证明了经验谱近似的一致收敛性（Theorem 3.1），从而保证了检验的渐近有效性。同时，本文开发了自适应部分特征分解算法（\(O(k n^2)\)）和收缩校正，在计算效率和尾部精度上均优于现有非蒙特卡洛方法。

子线索聚类

被引文献大致落在三条子线索上：

  1. 距离协方差的定义与性质：Székely et al. (2007) [19]（原始定义）、Bottcher et al. (2017) [2]（广义距离协方差与 Lévy 测度框架）、Sejdinovic et al. (2013) [16]（与 HSIC 等价性）、Edelmann & Goeman (2022) [5]（回归视角）。这一簇主要关注识别与表示，不直接处理零分布计算。
  2. 零分布的矩匹配与保守近似：Huang & Huo (2021) [8]（Gamma 近似）、Berschneider & Bottcher (2018) [1]（BB2/BB3）、Shen et al. (2022) [17]（卡方检验）、Székely et al. (2007) [19] 中的 SRB。这一簇追求计算速度，但牺牲了尾部精度或渐近精确性。
  3. 谱方法与快速计算：Huo & Székely (2016) [9]（\(O(n \log n)\) 快速算法用于一维）、Gretton et al. (2009) [7]（HSIC 的谱近似，无严格证明）、Jakobsen (2017) [11]（度量空间中的距离协方差渐近分布）。本文属于这一簇，但提供了首个严格证明和自适应算法。

这个方向在追问的核心问题

  1. 如何用样本特征值一致地估计加权卡方和的分布函数？ 即，当用经验谱 \(\hat{\lambda}_n\) 代替总体谱 \(\lambda\) 时，\(\sup_c |\hat{F}_n(c) - F_0(c)| \to 0\) 是否成立？需要什么条件？
  2. 如何避免全谱分解（\(O(n^3)\)）而仍能获得精确的 p 值？ 能否利用部分特征值给出 p 值的可计算上下界，并在界足够紧时停止？
  3. 如何校正有限样本偏差？ 经验谱的矩（尤其是二阶矩）是总体矩的有偏估计，能否通过收缩校正匹配无偏矩估计，从而改善小样本性能？
  4. 能否将谱方法推广到其他退化 U-统计量？ 距离协方差是 6 阶 U-统计量，其渐近分布是退化（degenerate）的。其他退化 U-统计量（如能量距离、某些核检验）是否也能用类似方法？

已知瓶颈：现有矩匹配方法在尾部精度差（Gamma 反保守，SPV/BB2 保守），而全谱分解计算成本高。本文的谱方法理论上解决了尾部精度问题，但小样本（\(n \le 50\)）下表现仍弱于 BB3（见 Table 1）。

⚠️ 作者的 framing

作者将缺口 frame 为：“虽然谱近似在 HSIC 中已有使用，但缺乏严格的理论证明”（Introduction 第 2 段：“a comprehensive theoretical justification of this approach is still lacking”）。因此，本文的“显然的下一步”是：给出该近似的严格理论证明，并开发实用的计算算法。

被淡化或回避的竞争路线： - 作者承认 BB3 在小样本下表现最好（Section 5.2：“BB3 typically shows the best performance for small sample sizes (n ≤ 50)”），但未深入讨论为何谱方法在小样本下弱——可能因为经验谱的估计误差在小样本下较大，而矩匹配方法（尤其是三阶矩）更稳健。作者仅在 Discussion 中建议小样本用置换检验或 BB3。 - 作者未提及随机投影方法（如 Huang & Huo 2017 [6] 的 RPDC），该方法通过随机投影将计算复杂度降至 \(O(nK \log n)\)，且可处理多变量。这可能是因为 RPDC 不直接近似零分布，而是通过投影后的距离协方差检验，与本文的谱方法思路不同。

什么明显该被引 / 该存在、却没出现在 intro 里？ - 关于退化 U-统计量的谱分解的经典文献（如 Serfling 1980, Lee 1990）未被引用。这些文献提供了 U-统计量渐近分布的一般理论（特征函数展开），本文的 Theorem 2.1 本质上是该理论在距离协方差上的应用。作者引用了 Jakobsen (2017) [11] 的硕士论文，但未引用更标准的教科书。 - 计算加权卡方和分布函数的数值算法（如 Imhof 1961, Davies 1980, Ruben 1962）在 Section 4 的 Remark 4.4 中被提及，但未在 intro 中作为背景介绍。这些算法是本文实现的基础。

张力

未见明显对立引用。各被引工作基本是互补的：有的关注定义，有的关注近似，有的关注计算。唯一可视为“张力”的是：矩匹配方法（Gamma, BB3）声称在尾部有效，但本文模拟显示它们在极小 p 值下偏差显著（Gamma 因子高达 72），而谱方法则收敛到名义水平。这并非矛盾，而是不同方法在不同条件下的表现差异。

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

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

  • 符号：
  • \(X, Y\)：取值于可分离度量空间 \((\mathcal{X}, \rho_X)\) 和 \((\mathcal{Y}, \rho_Y)\) 的随机变量（或向量）。
  • \(d_X, d_Y\)：定义在 \(\mathcal{X} \times \mathcal{X}\) 和 \(\mathcal{Y} \times \mathcal{Y}\) 上的负型距离（negative type distance），即对任意有限点集和零和系数 \(a_i\)，有 \(\sum_{i,j} a_i a_j d(z_i, z_j) \le 0\)。例如欧氏距离、高斯距离 \(1 - e^{-(x-y)^2/(2h^2)}\)。
  • \(P_X, P_Y\)：\(X\) 和 \(Y\) 的边缘分布。
  • \(V^2(d_X, d_Y; X, Y)\)：广义距离协方差（总体量），定义为六重积分（式 (1)）。当 \(d_X, d_Y\) 为欧氏距离时退化为经典距离协方差。
  • \(\hat{V}^2_n(X,Y)\)：样本 V-统计量（式 (4) 的迹形式），\(\hat{U}^2_n(X,Y)\)：样本 U-统计量。
  • \(A_n, B_n\)：\(n \times n\) 双中心距离矩阵（式 (4)），其元素为 \(d_X(X_i, X_j)\) 减去行均值、列均值、总均值后的残差。\(A_n \mathbf{1} = B_n \mathbf{1} = 0\)，秩 \(\le n-1\)。
  • \(\hat{\lambda}^X_{n1} \ge \cdots \ge \hat{\lambda}^X_{n,n-1} \ge \hat{\lambda}^X_{nn}=0\)：\(-n^{-1}A_n\) 的特征值（非负，因为 \(d_X\) 为负型）。类似定义 \(\hat{\lambda}^Y_{nj}\)。
  • \(\lambda^X_i, \lambda^Y_j\)：总体特征值，来自积分算子 \(T_X, T_Y\)（Theorem 2.1）。
  • \(Z_{ij}\)：i.i.d. 标准正态随机变量。
  • \(F(c; \mu_X, \mu_Y) = P(\sum_{i,j} \mu^X_i \mu^Y_j (Z_{ij}^2 - 1) \le c)\)：U-统计量版本的极限分布函数；\(G(c; \mu_X, \mu_Y) = P(\sum_{i,j} \mu^X_i \mu^Y_j Z_{ij}^2 \le c)\)：V-统计量版本的极限分布函数。
  • \(\hat{F}_n(c) = F(c; \hat{\lambda}^X_n, \hat{\lambda}^Y_n)\)，\(\hat{G}_n(c) = G(c; \hat{\lambda}^X_n, \hat{\lambda}^Y_n)\)：用样本特征值替换总体特征值得到的经验分布函数。

  • \(F_0(c) = F(c; \lambda^X, \lambda^Y)\)，\(G_0(c) = G(c; \lambda^X, \lambda^Y)\)：真实极限分布函数。

  • 模型：

  • 数据生成：\((X_i, Y_i) \overset{i.i.d.}{\sim} P_{XY}\)，其中 \(P_{XY}\) 是联合分布。零假设 \(H_0: X \perp Y\)（独立）。
  • 距离 \(d_X, d_Y\) 是预先选定的负型距离，连续且满足可积性条件（式 (7)）。

  • 总体特征值 \(\lambda^X_i, \lambda^Y_j\) 由积分算子 \(T_X, T_Y\) 定义，这些算子依赖于边缘分布 \(P_X, P_Y\) 和距离函数。

  • 可观测数据：

  • 可观测：样本 \((X_i, Y_i)_{i=1}^n\)，以及由此计算的双中心距离矩阵 \(A_n, B_n\)（及其特征值 \(\hat{\lambda}^X_{ni}, \hat{\lambda}^Y_{nj}\)）。
  • 不可观测：总体特征值 \(\lambda^X_i, \lambda^Y_j\)，以及极限分布函数 \(F_0, G_0\)。检验的目标是用 \(\hat{F}_n\) 或 \(\hat{G}_n\) 来近似 \(F_0\) 或 \(G_0\)，从而计算 p 值。

第二步：最小内核

考虑最简特例：\(X\) 和 \(Y\) 是独立的一维标准正态随机变量，使用欧氏距离 \(d_X(x_1, x_2) = |x_1 - x_2|\)，\(d_Y\) 同理。此时经典距离协方差（Székely et al. 2007）的 V-统计量为：

\[n \hat{V}^2_n = \frac{1}{n} \sum_{i,j=1}^n (A_n)_{ij} (B_n)_{ij},\]
其中 \(A_n\) 是 \(|X_i - X_j|\) 的双中心矩阵。Theorem 2.1 告诉我们，在独立下，
\[n \hat{V}^2_n \xrightarrow{D} \sum_{i,j=1}^\infty \lambda^X_i \lambda^Y_j Z_{ij}^2,\]
其中 \(\lambda^X_i\) 是积分算子 \((T_X f)(x_1) = \int D_X(x_1, x_2) f(x_2) dP_X(x_2)\) 的特征值，\(D_X(x_1, x_2) = \int (-|x_1 - x_2| + |x_3 - x_2| + |x_1 - x_4| - |x_3 - x_4|) dP_X(x_3) dP_X(x_4)\)。对于标准正态，这些特征值可以显式计算（但通常不必要）。

核心想法：我们无法知道 \(\lambda^X_i, \lambda^Y_j\)，但可以用样本特征值 \(\hat{\lambda}^X_{ni}, \hat{\lambda}^Y_{nj}\)（即 \(-n^{-1}A_n\) 和 \(-n^{-1}B_n\) 的特征值）来替换它们，得到 \(\hat{G}_n(c) = P(\sum_{i,j=1}^{n-1} \hat{\lambda}^X_{ni} \hat{\lambda}^Y_{nj} Z_{ij}^2 \le c)\)。Theorem 3.1 断言：在可积性条件下，\(\sup_c |\hat{G}_n(c) - G_0(c)| \to 0\) a.s.。这意味着，只要样本量足够大，用样本特征值构造的分布函数 \(\hat{G}_n\) 可以一致地逼近真实极限分布 \(G_0\)，从而检验的拒绝域 \(\{\hat{G}_n^{-1}(1-\alpha) < n\hat{V}^2_n\}\) 是渐近有效的（Corollary 3.2）。

为什么这个特例抓住了核心：即使在一维正态、欧氏距离的最简单情形，总体特征值也是未知的，必须用样本特征值近似。本文的全部理论贡献就在于证明这种近似的一致性，而计算上的挑战（全谱分解 \(O(n^3)\)）在这个特例中同样存在。因此，理解这个特例就理解了论文的数学本质：用经验谱代替总体谱，并证明这种代替不会破坏检验的渐近水平。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：广义距离协方差（包括 HSIC 作为特例）在独立零假设下的 p 值计算问题——如何用双中心距离矩阵的经验谱直接近似其加权卡方极限分布，并保证检验的渐近有效性。
  2. 核心工具/方法：① 严格证明经验谱近似的一致收敛性（Theorem 3.1），基于负型距离的谱分解和 U-统计量的中心极限定理；② 自适应部分特征分解算法，利用弱优超（majorization）给出 p 值的可计算上下界，将复杂度从 \(O(n^3)\) 降至 \(O(k n^2)\)；③ 收缩校正方法，匹配无偏矩估计以改善有限样本精度。
  3. 主要结论：在 mild 的可积性和连续性条件下，用样本特征值构造的分布函数 \(\hat{F}_n, \hat{G}_n\) 一致收敛到真实极限分布 \(F_0, G_0\)，从而检验是渐近有效的。模拟表明，该方法是唯一在经验第一类错误收敛到名义水平上表现稳定的非蒙特卡洛程序（对于 \(n \ge 100\)），且自适应算法大幅降低了计算时间。

关键设定与假设

  • 距离的负型性：\(d_X, d_Y\) 为负型距离（negative type）。这是保证双中心矩阵 \(-n^{-1}A_n\) 半正定的关键，也是特征值非负的前提。相比经典距离协方差（仅欧氏距离），本文允许更一般的距离（如高斯距离、Minkowski 距离）。
  • 可积性与连续性：\(\int d_X(x_1, x_2) dP_X(x_1) dP_X(x_2) < \infty\)（式 (7)），且 \(d_X, d_Y\) 关于乘积拓扑连续。这些条件在已有文献中常被省略（作者在 Section 2 明确指出：“The measurability and continuity conditions given in this paragraph are typically omitted in the literature”），但本文认为它们是 CLT 和谱一致性的必要条件。
  • 可分离度量空间：\(\mathcal{X}, \mathcal{Y}\) 是可分离的，以保证 Borel \(\sigma\)-代数的良好性质，并使得积分算子 \(T_X, T_Y\) 的谱分解成立。
  • 独立性：Theorem 2.1 和 Corollary 3.2 要求 \(X \perp Y\)（零假设下）。但 Theorem 3.1 本身不要求独立性——它只断言经验谱一致估计总体谱，无论 \(X, Y\) 是否独立。这保证了检验在备择假设下也能正确计算 p 值（虽然此时 p 值可能不服从均匀分布，但检验的 size 由零假设下的行为决定）。

相比已有文献的放宽/强化： - 相比 Székely et al. (2007) [19]：距离类从欧氏距离推广到一般负型距离；给出了更一般的 CLT（Theorem 2.1）并明确了可测性条件。 - 相比 Sejdinovic et al. (2013) [16]：后者建立了距离协方差与 HSIC 的等价性，但未处理零分布近似；本文直接利用该等价性，将结果覆盖到 HSIC。 - 相比 Gretton et al. (2009) [7]：后者在 HSIC 中使用了谱近似但无严格证明；本文提供了完整证明。

主要结果

  • Theorem 2.1（渐近分布）：在独立和可积条件下，\(n \hat{U}^2_n \xrightarrow{D} \sum_{i,j} \lambda^X_i \lambda^Y_j (Z_{ij}^2 - 1)\)，\(n \hat{V}^2_n \xrightarrow{D} \sum_{i,j} \lambda^X_i \lambda^Y_j Z_{ij}^2\)。该定理是后续所有结果的基础。技术难点：需要处理退化 U-统计量的谱分解，并证明特征值 \(\lambda^X_i, \lambda^Y_j\) 的求和有限（即 \(\sum_i \lambda^X_i < \infty\)）。作者通过迹恒等式证明这一点（见证明中“trace identities”）。
  • Theorem 3.1（经验谱一致性）：在式 (7) 下，存在概率为 1 的集合 \(\Omega_0\)，使得在 \(\Omega_0\) 上，\(\sup_c |\hat{F}_n(c) - F_0(c)| \to 0\) 且 \(\sup_c |\hat{G}_n(c) - G_0(c)| \to 0\)。直觉：样本特征值 \(\hat{\lambda}^X_{ni}\) 是总体特征值 \(\lambda^X_i\) 的一致估计（在 \(\ell_1\) 意义下），且加权卡方和的分布函数关于权重序列是 Lipschitz 的（在 \(\ell_1\) 度量下）。必要条件：式 (7) 保证总体特征值可求和，从而极限分布良定义。解决的技术难点：需要证明经验谱在 \(\ell_1\) 范数下收敛到总体谱，这比逐点收敛更强。作者利用负型距离的 Hilbert 空间嵌入和 U-统计量的强相合性来证明。
  • Corollary 3.2（检验渐近有效性）：在独立和式 (7) 下，对于任意 \(\alpha \in (0,1)\)，\(P(n \hat{U}^2_n > \hat{F}_n^{-1}(1-\alpha)) \to \alpha\)，对 \(\hat{V}^2_n\) 类似。这是 Theorem 2.1 和 Theorem 3.1 的直接推论，因为 \(\hat{F}_n^{-1}(1-\alpha) \to F_0^{-1}(1-\alpha)\) 且 \(n \hat{U}^2_n\) 的分布收敛到 \(F_0\)。
  • 自适应算法（Section 4.1）：通过计算前 \(k\) 个特征值，利用弱优超性质（Proposition 4.1）得到 p 值的下界 \(p_{\text{anti}}\) 和上界 \(p_{\text{cons}}\)（当 \(t_{\text{obs}} \ge 2m_1\) 时）。当界足够紧（如 \(p_{\text{cons}}/p_{\text{anti}} \le \tau_{\text{tol}}\)）或可判定显著性时停止。复杂度 \(O(k n^2)\)。
  • 收缩校正（Section 4.2）：将特征值 \(\hat{\lambda}_{ij}\) 向均值收缩，使得收缩后的二阶矩等于无偏估计 \(\tilde{\sigma}^2\)。Proposition 4.3 保证收缩后的特征值仍为正且和不变。模拟表明收缩版本优于朴素版本。

证明路线与技术技巧

Theorem 3.1 的证明路线（根据 Supplementary Material 的线索推断，论文正文未给出完整证明，但给出了关键步骤）：

  1. 将经验谱收敛转化为算子收敛：定义经验算子 \(\hat{T}_X^{(n)} f(x) = \frac{1}{n} \sum_{j=1}^n D_X(x, X_j) f(X_j)\)，其核为 \(D_X(x_1, x_2) = \int (-d_X(x_1, x_2) + d_X(x_3, x_2) + d_X(x_1, x_4) - d_X(x_3, x_4)) dP_X(x_3) dP_X(x_4)\)。样本特征值 \(\hat{\lambda}^X_{ni}\) 是 \(\hat{T}_X^{(n)}\) 的特征值（在 \(L^2(P_X)\) 中）。总体特征值 \(\lambda^X_i\) 是 \(T_X\) 的特征值。
  2. 证明 \(\hat{T}_X^{(n)}\) 在 Hilbert-Schmidt 范数下收敛到 \(T_X\)：利用 U-统计量的强相合性，证明 \(\| \hat{T}_X^{(n)} - T_X \|_{\text{HS}} \to 0\) a.s.。这需要核 \(D_X\) 的平方可积性，由式 (7) 保证。
  3. 由算子收敛推出特征值在 \(\ell_1\) 下的收敛：Hilbert-Schmidt 算子的特征值在 \(\ell_1\) 范数下是连续的（Weyl 不等式 + 迹范数控制）。具体地，\(\sum_i |\hat{\lambda}^X_{ni} - \lambda^X_i| \le \| \hat{T}_X^{(n)} - T_X \|_{\text{HS}} \cdot \text{rank}\) 的某种界，但需要更精细的论证（因为迹范数可能发散）。作者可能使用了 Hoffman-Wielandt 型不等式或更直接的 \(\ell_1\) 收敛引理。
  4. 由特征值 \(\ell_1\) 收敛推出分布函数一致收敛：对于加权卡方和 \(\sum_{i,j} \mu^X_i \mu^Y_j Z_{ij}^2\)，其分布函数 \(G(c; \mu^X, \mu^Y)\) 关于权重序列 \((\mu^X, \mu^Y)\) 在 \(\ell_1 \times \ell_1\) 度量下是 Lipschitz 的（因为 \(\sum_{i,j} |\mu^X_i \mu^Y_j - \nu^X_i \nu^Y_j| \le \sum_i |\mu^X_i - \nu^X_i| \sum_j \mu^Y_j + \sum_j |\mu^Y_j - \nu^Y_j| \sum_i \nu^X_i\)）。因此，\(\hat{\lambda}^X_n \to \lambda^X\) 在 \(\ell_1\) 中且 \(\hat{\lambda}^Y_n \to \lambda^Y\) 在 \(\ell_1\) 中，推出 \(\sup_c |\hat{G}_n(c) - G_0(c)| \to 0\)。

关键跳跃点： - 从经验谱到总体谱的 \(\ell_1\) 收敛：这是最吃劲的部分。通常特征值收敛是在逐点意义下（如 \(\hat{\lambda}_{n1} \to \lambda_1\)），但这里需要整个序列的和收敛。作者利用负型距离的特殊结构（双中心矩阵的迹等于距离平方和的可积形式）来证明 \(\sum_i \hat{\lambda}^X_{ni} \to \sum_i \lambda^X_i\) a.s.，再结合逐点收敛得到 \(\ell_1\) 收敛。 - 分布函数关于权重序列的 Lipschitz 性质：需要证明 \(\sup_c |G(c; \mu) - G(c; \nu)| \le C \| \mu - \nu \|_1\)。这依赖于加权卡方和尾概率的指数界（如 Székely & Bakirov 2003 [18] 的极值概率结果），作者引用了该文献。

技术技巧点名： - U-统计量的强相合性：用于证明经验算子 \(\hat{T}_X^{(n)}\) 的 Hilbert-Schmidt 范数收敛。 - Hilbert-Schmidt 算子谱理论：用于建立特征值与算子核的关系。 - 弱优超（majorization）：Proposition 4.1 引用 Székely & Bakirov (2003) [18]，用于构造 p 值的上界。 - Lanczos 算法：用于部分特征分解，复杂度 \(O(k n^2)\)。 - 收缩估计：式 (14) 的收缩形式，类似于 James-Stein 型收缩，但针对特征值平方和。

真实例子与应用

本文有模拟实验（Section 5），无真实数据例子。模拟设置： - 数据：独立的标准正态 \(X, Y\)（零假设下），样本量 \(n = 10, 20, 50, 100, 200, 500\)。 - 方法对比：Gamma, BB2, BB3, SPV, SRB, Spectral (naive), Spectral (shrinkage)。其中 Spectral (shrinkage) 使用完整特征分解 + 收缩校正；Spectral (naive) 使用完整特征分解但不收缩。 - 评价指标：经验第一类错误率（以名义水平 \(\alpha\) 的倍数给出），\(\alpha = 0.05, 0.005, 0.0005, 5\times 10^{-5}, 5\times 10^{-6}\)。每个场景 1000 万次模拟。 - 结果（Table 1 和 Table 2）： - 对于经典距离协方差（Table 1）：当 \(n \ge 100\) 时，Spectral (shrinkage) 的经验第一类错误最接近名义水平（因子在 0.97–1.01 之间），而 Gamma 在 \(\alpha = 5\times 10^{-6}\) 时因子高达 72.06，BB3 因子在 1.3–2.0 之间。对于 \(n=10\)，BB3 表现最好。 - 对于高斯距离（Table 2）：类似模式，但 Gamma 的 anti-conservative 程度稍低（因子最高 13.96），Spectral (shrinkage) 仍是最接近名义水平的。 - 计算时间（Figure 1）：Spectral (first 100) 在 \(n=32000\) 时约 3 分钟，而 Spectral (Complete) 超过 3 小时，BB3 约 21 分钟。Gamma 在经典距离下利用 \(O(n \log n)\) 算法极快（<0.5 秒 for \(n=10^6\)），但在高斯距离下为 \(O(n^2)\)，与 Spectral (first 100) 相近。 - 这个例子想说明什么：① 谱方法（尤其是带收缩的）在中等到大样本下是唯一能精确控制第一类错误到名义水平的非蒙特卡洛方法；② 自适应部分特征分解可以大幅降低计算时间，使其在 \(n\) 很大时仍可行；③ 小样本下谱方法不如 BB3，建议使用置换检验或 BB3。

🔎 结论是否比证明窄

  • Theorem 3.1 的证明依赖于式 (7) 的可积性条件，但作者在 Discussion 中声称“the results transfer directly to kernel-based independence testing”（因为 HSIC 等价于广义距离协方差）。然而，HSIC 通常使用有界核（如高斯核），其可积性自动满足，因此转移是合理的。但若核无界（如多项式核），式 (7) 可能不成立，此时 Theorem 3.1 是否仍成立？作者未讨论。
  • Corollary 3.2 要求独立性，但 Theorem 3.1 不要求。作者在 Section 3 明确说：“Note that Theorem 3.1 does not require X and Y to be independent”。因此，检验的渐近有效性只在零假设下成立，但经验谱的一致性在备择下也成立——这意味着 p 值的计算在备择下也是合理的（虽然此时 p 值不服从均匀分布，但检验的 power 分析需要另外的理论，本文未涉及）。
  • 自适应算法的上界 \(p_{\text{cons}}\) 要求 \(t_{\text{obs}} \ge 2m_1\)（Corollary 4.2）。当 \(t_{\text{obs}} < 2m_1\) 时，作者提出用 \(p_{\text{anti}} > \tau_{\text{large}}\) 或 \(R/m_1 < \tau_{\text{conv}}\) 来停止，并用式 (13) 的分布近似。但式 (13) 的近似（将剩余特征值视为常数 \(R\)）缺乏理论保证——它相当于假设剩余特征值全部相等且独立于已计算部分，这仅在剩余特征值很小时才合理。作者在模拟中使用了完整特征分解，未测试自适应算法的实际 p 值精度，因此该近似的误差未知。

四、开放问题

  1. 大样本下的计算瓶颈：本文的自适应算法仍需存储 \(n \times n\) 距离矩阵，对于 \(n > 10^5\) 可能内存不足。作者在 Discussion 中提出两个方向：① 对观测值分箱/取整，将不同值个数降至 \(m \ll n\)，只需 \(m \times m\) 距离矩阵和 \(m \times m\) 列联表；② 用有限个特征近似核（如随机傅里叶特征），将复杂度降至 \(k^2 n\)。这两个方向均未在本文中实现或分析，是直接的后续工作。扎根点：Discussion 第 2 段。

  2. 小样本性能改进：谱方法在 \(n \le 50\) 时表现弱于 BB3。作者建议“incorporating estimates of the third moment into the spectral approaches”，即用三阶矩校正谱分布。这需要推导三阶矩的无偏估计（类似 Berschneider & Bottcher [1] 对前两阶矩的工作），并设计相应的收缩或调整方法。扎根点：Discussion 第 3 段：“The weak performance of the spectral algorithms for very small sample sizes may be improved by finding ways to incorporate estimates of the third moment into the spectral approaches”。

  3. 推广到其他退化 U-统计量：作者在 Discussion 中推测“the theoretical derivation of our approximation results extends in a straightforward manner to many other degenerate U- and V-statistics”。但退化 U-统计量的渐近分布形式依赖于核的谱分解，不同核的谱性质可能不同（如特征值衰减速度）。需要一般性条件（如核的 Hilbert-Schmidt 性质、特征值可和性）来保证经验谱一致性。扎根点：Discussion 最后一段。

  4. 自适应算法的理论保证：当 \(t_{\text{obs}} < 2m_1\) 时，作者用式 (13) 的分布（将剩余特征值视为常数）近似，但未给出该近似的误差界。能否证明在 \(R/m_1\) 很小时，该近似的 Kolmogorov 距离有界？或者能否构造更紧的上下界（如利用剩余特征值的最大值而非常数）？扎根点：Section 4.1 中 Case 2 的处理方式，以及 Corollary 4.2 仅适用于 \(t_{\text{obs}} \ge 2m_1\) 的限制。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论