技术摘要：高效且稳定的多维 Kolmogorov-Smirnov 距离

问题陈述

本文探讨了将 Kolmogorov-Smirnov (KS) 距离（一种用于比较单变量分布的基础非参数度量）扩展到多维设置（$d > 1$）时面临的挑战。虽然单变量 KS 距离已得到充分理解、具有稳定性且计算高效，但现有的高维推广版本存在显著局限性：

1. 不稳定性： 像 “quad-KS”（它将搜索空间限制在由数据点定义的象限内）这样的流行启发式方法被证明是不稳定的；仅仅增加或删除一个数据点，距离就会发生剧烈变化，这阻碍了严谨样本复杂度界的建立。
2. 计算不可行性： 在所有可能的范围内精确计算多维 KS 距离在计算上是非常昂贵的（朴素情况下为 $O(n^d)$），并且许多现有的基于排列的检验需要相对于样本量呈指数级增长的时间。
3. 单位敏感性： 许多替代度量（例如 Wasserstein, Maximum Mean MMD）依赖于欧几里得基底距离，这使得它们对单位选择或维度的缩放非常敏感，当维度具有不同的物理单位（例如身高与体重）时，这是一个问题。

作者提出了一种多维 KS 距离（$dKS$）的公式化形式，该形式是一种积分概率度量 (IPM)，对单位选择具有不变性，并且能够以带有可证明近似保证的方式高效计算。

方法论

1. 多维 KS ($dKS$) 的定义

作者将两个分布 $\mu$ 和 $\nu$ 在 $\mathbb{R}^d$ 中的距离定义为它们在正交支配矩形范围 (orthogonal dominating rectangular ranges) 上累积分布函数的最大差异。
$$dKS(\mu, \nu) = \sup_{z \in \mathbb{R}^d} \left| \int_{x \preceq z} d\mu(x) - \int_{x \preceq z} d\nu(x) \right|$$
其中 $x \preceq z$ 表示 $x$ 的每个坐标都小于或等于 $z$ 对应的坐标。与之前的一些扩展（例如 Peacock 的扩展，它考虑所有 $2^d$ 个象限）不同，该公式专注于单个象限（支配矩形），作者认为这足以构成一个鲁棒的度量。

2. 理论性质

• 度量性质： 论文证明了 $dKS$ 是概率测度空间上的一个完整度量（满足对称性、三角不等式和强恒等性），而不像某些启发式变体可能仅是伪度量或缺乏稳定性。
• 样本复杂度： 利用范围空间的 VC 维理论，作者确定了 $n = O(\frac{1}{\epsilon^2}(d + \log(1/\delta)))$ 个样本足以在误差 $\epsilon$ 内以概率 $1-\delta$ 估计该距离。该界限与维度 $d$ 成线性关系。

3. 计算算法

论文引入了算法来计算 $dKS$的$\epsilon$-近似，其计算-统计运行时间 (CSR) 在维度 $d \le 4$ 时接近于所需样本量的近线性水平。

• 对于 $d=2$： 作者提出了一个草图法 (sketching approach)（算法 2, dKS-Sketch）。通过对点进行排序并构建大小为 $O((d/\epsilon)^d)$ 的分层网格，算法将问题简化为在网格上的动态规划。
  • 运行时间： $O(n \log n + (d/\epsilon)^d)$。对于 $d=2$ 且 $\epsilon \approx 1/\sqrt{n}$，这产生了 $O(n \log n)$ 的复杂度。
• 对于 $d=3, 4$： 作者将问题归约为寻找一组加权矩形中的最大深度点问题（Klee 测度问题的一个变体）。
  • 他们首先使用低差异着色（引理 2）将样本压缩到一个较小的 $\epsilon$-近似集。
  • 然后应用 Chan 算法在 $O(s^{d/2} \text{polylog}(s))$ 时间内找到最大权重点，其中 $s$ 是压缩后的样本量。
  • 运行时间： 在样本复杂度 $n_\epsilon$ 中接近线性。具体而言，对于 $d=3$ 为 $O(n \log^3 n)$，对于 $d=4$ 为 $O(n \log^{21} n)$。
• 硬度： 论文指出，对于 $d > 4$，实现近线性运行时间是不太可能的，因为这将意味着在解决 Max-Weight $k$-Clique 问题方面取得突破，这是一个广泛公认的复杂问题。

4. 假设检验

利用导出的样本复杂度界限和度量性质，作者构建了一个 level-$\delta$ 两样本假设检验。

• 如果计算出的 $dKS$超过了由样本量和置信水平导出的阈值，则拒绝原假设（$\mu = \nu$）。
• 至关重要的是，不同于基于蒙特卡洛的检验，该检验提供了一个精确的、有限样本的保证，关于第一类错误率，而无需依赖渐近近似。

关键结果

1. 稳定性： 所提出的 $dKS$ 公式在采样方面是稳定的，不像 “quad-KS” 或其他象限限制的启发式方法。作者构造了病态示例，显示在 quad-KS 计算中增加一个点会导致距离翻倍，而 $dKS$ 保持稳定。
2. 效率：
   • $d=2$： 实现了 $O(n \log n)$ 的运行时间，匹配了单变量情况的效率。
   • $d=3, 4$： 在样本复杂度中实现了近线性运行时间，相比于以往精确方法的指数级或高多项式成本，这是一个显著的改进。
3. 精确性： 导出的假设检验是第一个为中等维度（$d \le 4$）的多维分布提供精确、非渐近且非基于模拟的检验。
4. 实证验证： 在 $d=2$ 数据上的实验表明，dKS-Sketch 算法比基准精确算法快几个数量级（例如，对于 $n \approx 10^6$，耗时 0.2s 对比 4.2 小时），同时保持了相当的准确性。在功效评估中，基于草图的检验在数秒内即可实现完全的统计功效，而基于排列的基准方法则需要数小时甚至数天。

重要性与主张

论文声称通过在数学严谨性（稳定性、度量性质、样本复杂度）与计算可行性之间取得平衡，提供了将 KS 距离推广到多维的“正确方式”。

• 理论贡献： 它确立了一个单象限公式足以构成鲁棒度量，并证明了该度量在低维情况下允许高效的近似算法。
• 实际影响： 它使得在具有不同单位的中等维度数据（例如 2D 到 4D）上应用非参数两样本检验成为可能，在这些场景下，基于欧几里得的度量会失效，而之前的 KS 扩展要么不稳定，要么计算成本过高。
• 局限性： 作者明确指出，对于 $d > 4$ 的维度，除非解决重大计算复杂度理论猜想，否则该问题在近线性运行时间内可能是难以处理的。他们还承认，针对 $d=3, 4$ 的算法依赖于向 Klee 测度问题的复杂归约，与 $d=2$ 的情况相比，实际实现可能较为困难。

这项工作将所提出的 $dKS$ 定位为现有高维扩展的优选替代方案，为中等维度的统计分析提供了一个稳定、精确且计算高效的工具。