技术摘要：优化 Wasserstein 距离估计的计算 - 统计运行时

问题陈述

平方 Wasserstein 距离 $W_2^2(P, Q)$ 是衡量 $\mathbb{R}^d$ 中概率分布 $P$ 与 $Q$ 之间差异的标准度量。在实际数据分析和机器学习任务（例如参数估计、假设检验）中，这些分布是未知的，必须从大小为 $n$ 的经验样本 $\hat{P}_n$ 和 $\hat{Q}_n$ 中进行估计。

现有方法面临一个根本性的瓶颈：精确计算或计算带有加性误差 $\epsilon$ 的 $W_2^2(\hat{P}_n, \hat{Q}_n)$ 通常所需的运行时随 $n$ 和 $\epsilon$ 表现不佳（例如 $O(n^2/\epsilon^2)$ 或更差）。相反，完全依赖经验测度收敛率的纯统计方法往往忽略了在由此产生的大规模数据集上求解最优传输问题的计算成本。

本文解决了**计算 - 统计运行时（CSR）**问题。目标是设计一种随机算法，以期望值在 $\epsilon$ 加性误差范围内估计 $W_2^2(P, Q)$，其中运行时 $O(f(\epsilon))$ 同时考虑了收集样本的成本（假设每个样本为 $O(1)$）和计算成本。作者认为，目标精度应与样本量引起的统计误差相一致，而不是将经验测度视为真实值。

方法论：采样 - 草图 - 求解范式

作者提出了一种三阶段范式，以实现快速的 CSR，特别是针对定义域 $(0, 1)^d$ 上具有 Hölder 平滑密度的分布：

1. 采样（Sample）： 从 $P$ 和 $Q$ 中收集 $n$ 个随机样本，形成经验测度 $\hat{P}_n$ 和 $\hat{Q}_n$。
2. 草图（Sketch）： 将这些样本映射到规则笛卡尔网格 $G_h$ 上，网格单元宽度为 $h = \Theta(\epsilon^{-\frac{1}{1+\alpha}})$。网格单元内的所有质量被坍缩到单元中心。这生成了压缩后的离散测度 $G_h\#\hat{P}_n$ 和 $G_h\#\hat{Q}_n$。
3. 求解（Solve）： 利用一种专门利用规则网格结构的算法，计算草图测度之间的精确平方 Wasserstein 距离。

关键技术组件

1. 基于网格的离散化误差界（第 2 节）

本文建立了一个关于将质量坍缩到网格中心所引入的近似误差的新上界。

• 假设： $P$ 和 $Q$ 具有 $\alpha$-Hölder 平滑密度（$0 < \alpha < 1$），且远离零和无穷大。
• 结果： 作者证明了 $|W_2^2(G_h\#P, G_h\#Q) - W_2^2(P, Q)| \leq K h^{1+\alpha}$。
• 机制： 与产生 $O(h)$ 的标准三角不等式论证不同，该结果利用了基于Brenier 映射（最优传输映射）正则性的新颖耦合论证。通过利用 Collins 和 Tong [2025] 关于 Brenier 映射全局 Hölder 连续性的最新结果，作者表明一阶误差项相互抵消（类似于中点法则），从而产生了更紧的 $O(h^{1+\alpha})$ 界。
• 非平滑情况： 对于没有平滑性假设的分布，该界回归到 $O(h)$，与标准三角不等式论证一致。

2. 规则网格上的高效精确计算（第 3 节）

一旦数据被草图化到规则网格上，问题的结构允许显著更快的精确计算。

• 结构： 草图测度由每个轴上有 $L$ 个划分的网格支持，其中每个原子的权重是 $1/n$ 的倍数。基础成本（平方欧几里得距离）在维度上是可分离的。
• 归约： 作者利用 Auricchio 等人 [2018] 的归约方法，将具有可分离成本的 $d$ 维直方图之间的最优传输问题转化为$(d+1)$-部图上的最小费用流问题。
• 算法： 通过缩放问题以确保整数需求、容量和成本，他们应用了 van den Brand 等人 [2023] 的确定性精确最小费用流算法。
• 复杂度： 草图上的精确计算运行时间为 $\tilde{O}(L^{d+1+o(1)})$。

3. 综合：CSR 算法（第 4 节）

最终算法结合了统计采样、网格草图化和快速求解器。

• 样本量： 样本数量 $n$ 的选择旨在平衡统计误差和离散化误差，通常为 $n = \tilde{O}(\epsilon^{-\max(2, d/2)})$。
• 网格分辨率： 网格大小设置为 $L = \Theta(\epsilon^{-\frac{1}{1+\alpha}})$。
• 总运行时： 组合运行时由求解器步骤主导，产生的计算 - 统计运行时为：
  $$\tilde{O}\left(\epsilon^{-\max\left(2, \frac{d+1+o(1)}{1+\alpha}\right)}\right)$$

主要结果与贡献

1. 平滑分布的改进运行时

本文表明，对于 $\alpha$-Hölder 平滑分布，CSR 可以接近最优，在特定情形下匹配 $\Omega(\epsilon^{-2})$ 的统计下界：

• 维度 $d=2$： 对于 $\alpha > 1/2$，该算法实现了 $\tilde{O}(\epsilon^{-2})$。这匹配了最优统计速率，意味着计算成本不超过收集足够样本的成本。
• 维度 $d=3$： 当 $\alpha \to 1$（Lipschitz 平滑）时，运行时接近 $\tilde{O}(\epsilon^{-2})$。对于一般的 $0 < \alpha < 1$，运行时为 $\tilde{O}(\epsilon^{-\frac{4}{1+\alpha}})$。
• 一般维度 $d$： 运行时为 $\tilde{O}(\epsilon^{-\max(2, \frac{d+1}{1+\alpha})})$。

2. 与先前工作的比较

作者在表 2 中将他们的结果与现有方法进行了比较：

• 经验插件 + Lahn 等人 [2019]： 在 $d=2$ 中实现 $\tilde{O}(\epsilon^{-4})$，在 $d=3$ 中实现 $\tilde{O}(\epsilon^{-5})$。
• 熵 OT / Sinkhorn (Chizat 等人 [2020])： 在 $d=2$ 和 $d=3$ 中实现 $\tilde{O}(\epsilon^{-6})$。
• 本文工作： 在 $d=2$ 中实现 $\tilde{O}(\epsilon^{-2})$（对于 $\alpha > 1/2$），在 $d=3$ 中实现 $\tilde{O}(\epsilon^{-2})$（当 $\alpha \to 1$ 时）。

3. 非平滑情况

在没有平滑性假设的情况下（$\alpha \to 0$），该方法产生的 CSR 为 $\tilde{O}(\epsilon^{-\max(2, d+1)})$。对于 $d=2$，这是 $\tilde{O}(\epsilon^{-3})$；对于 $d=3$，这是 $\tilde{O}(\epsilon^{-4})$。

意义与主张

本文声称其主要贡献是采样 - 草图 - 求解范式，该范式成功地将统计估计误差与传输问题的计算复杂度解耦。

• 无误差压缩： 作者表明，只要底层分布是平滑的，将样本映射到规则网格就可以压缩数据而不增加渐近误差。
• 正则化以加速： 网格结构对问题进行了正则化，使得能够使用快速精确流算法，而这些算法对于一般的离散点集是不可行的。
• 最优性： 该工作认为，对于低维（$d=2, 3$）中足够平滑的分布，在计算上实现 $\epsilon^{-2}$ 的最优统计速率是可能的。这挑战了计算 Wasserstein 距离本质上需要相对于所需精度具有超线性或超二次运行时这一观念。

作者明确指出，他们的结果依赖于 $P$ 和 $Q$ 支持在有界域（特别是 $(0, 1)^d$）上并具有 Hölder 平滑密度的假设。他们并未声称这些结果在不加修改的情况下扩展到非平滑分布或无界域。其意义在于弥合统计估计理论与计算最优传输之间的差距，表明在现实的平滑性假设下，“计算瓶颈”可以被有效消除。