Sample complexity of unbalanced entropic OT

技术摘要：非平衡熵正则化最优传输的样本复杂度

问题陈述
最优传输（Optimal Transport, OT）提供了一个比较概率测度的几何框架，但经典的平衡 OT 在机器学习应用中面临两个显著局限性：(1) 硬质量守恒约束过于僵化，不适用于存在质量缺失或产生的场景；(2) 存在不利的高维样本复杂度（“维度之咒”），即经验收敛速率随环境维度的增加而恶化。

虽然熵正则化和非平衡松弛（使用 $\phi$-散度）已分别用于解决这些问题，但现有的关于非平衡熵正则化 OT 的统计保证主要局限于标量传输值（目标函数）。目前缺乏直接针对**最优耦合（传输计划）**的高概率有限样本界。这一差距至关重要，因为在生成模型或轨迹推断等应用中，耦合本身才是预测和插值的研究对象，而非仅仅是代价函数。

方法论
本文通过关注对偶问题的几何特性，对非平衡熵正则化 OT 进行了统计分析。其核心方法论创新在于引入了**平移不变包络（translation-invariant envelope）**表述，以处理非平衡设置中固有的规范不变性（gauge invariance）缺失问题。

1. 对偶表述与包络构建：
   与平衡 OT 不同（在平衡 OT 中，对偶目标函数在 Kantorovich 势函数的加法平移 $f \to f+\lambda, g \to g-\lambda$ 下具有不变性），非平衡 OT 由于依赖于绝对势能水平的边缘散度惩罚，打破了这种对称性。作者定义了一个平移不变包络 $T_{\alpha, \beta}(f, g) := \inf_{\lambda \in \mathbb{R}} K_{\alpha, \beta}(f+\lambda, g-\lambda)$。这种构建方式明确地将对偶的内在自由度与伪平移方向分离出来。

2. 几何分析（紧致性与强凸性）：
   作者证明，在温和假设下（紧致空间、Lipschitz 代价），该包络泛函拥有一个紧致锚定极小化定义域（$P_{\alpha, \beta}^0$），其中势函数被固定为相对于源测度的零均值。至关重要的是，在该定义域上，该包络相对于加权 $L^2$ 范数是一致强凸的。这恢复了在标准非平衡对偶中丢失的有益几何结构。

3. 平移参数控制：
   虽然包络消除了对任意规范固定的需求，但它引入了对平移参数 $\lambda$ 的优化。本文建立在满足散度生成器温和定义域条件（假设 A2）的情况下，最优 $\lambda$ 被限制在一个一致有界的区间 $[-R, R]$ 内。这使得对偶势函数具备了一致 $L^\infty$ 界。

4. 统计稳定性：
   利用锚定包络的强凸性和平移参数的有界性，作者推导出了稳定性估计。他们证明了经验对偶势函数一致收敛于总体势函数。这些对偶收敛率随后通过指数缩放关系（$d\pi/d(\alpha \otimes \beta) \propto \exp((f \oplus g - c)/\eta)$）传递到原问题传输计划。

核心贡献

• 平移不变对偶表述： 本文引入了一种严谨的对偶表述，通过对平移方向进行商空间化处理，恢复了非平衡熵正则化 OT 的强凸性，这一性质此前仅被用于 Sinkhorn 迭代的算法稳定性。
• 计划层级的样本复杂度： 主要贡献在于推导了最优耦合（传输计划）在高概率下的有限样本界，而非仅仅是目标函数值。
• 通用散度适用性： 研究结果适用于广泛的 $\phi$-散度类（包括 KL、$\chi^2$、Hellinger、Jensen–Shannon 和 $\alpha$-散度），无需针对特定散度进行证明，而是依赖于通用的凸性和紧致性论证。
• 显式常数： 本文为平移参数及由此产生的样本复杂度提供了显式常数，阐明了其对熵参数 $\eta$、代价函数及散度特性的依赖关系。

主要结果
本文建立，对于由 $n$ 个样本得到的经验测度 $\alpha_n, \beta_n$，经验最优计划 $\pi_n$ 与总体计划 $\pi^\star$ 之间的偏差满足如下形式的高概率界：
$$|\langle h, \pi^\star - \pi_n \rangle| \lesssim C \cdot e^{C(M + \|c\|_\infty)/\eta} \|h\|_\infty \sqrt{\frac{m_\alpha m_\beta (\log n + t)}{n}}$$
其中 $M$ 是对偶势函数的一致界，$h$ 是测试函数，且常数取决于问题的几何结构和散度参数。值得注意的是，如果采样分布与边缘分布的乘积相匹配，则可以移除 $\log n$ 项。

意义与主张
本文的研究结果阐明了正则化在机器学习 OT 应用中的实际必要性。具体而言：

• 缓解维度问题： 正则化软化了维度之咒，减少了稳定估计传输所需的样本量。
• 算法兼容性： 所得估计量仍与可扩展的 Sinkhorn 类求解器兼容，弥合了统计理论与计算实践之间的鸿沟。
• 逆问题的稳定性： 提供的正向稳定性估计对于伴随的逆问题分析（例如从样本中恢复代价）至关重要，正如相关文献 [1] 所述。

作者强调，其分析依赖于“非常温和且在很大程度上与散度无关的假设”，这使得该理论框架具有鲁棒性，并适用于实践中的标准模型。他们并非声称解决了维度之咒，而是展示了非平衡熵正则化 OT 如何在处理高维设置时，成为一种统计上可处理的替代方案，优于未正则化的 Wasserstein 距离。