跳转至

Limit theorems for entropic optimal transport maps and Sinkhorn divergence

作者: Ziv Goldfeld, Kengo Kato, Gabriel Rioux, Ritwik Sadhu
来源: Electronic Journal of Statistics
主题: 非参数 / 半参数
相关性: 6/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

本方向研究熵正则化最优传输（Entropic Optimal Transport, EOT） 的统计推断理论。核心问题是：给定两个概率分布 \(P\) 和 \(Q\) 的独立同分布样本，如何对 EOT 映射（将 \(P\) 的样本“运输”到 \(Q\) 的对应点）、对偶势函数（EOT 问题的 Lagrange 乘子）以及 Sinkhorn 散度（EOT 代价的偏差修正版本）进行有效的统计推断——即构造置信区间、进行假设检验，并保证这些推断的渐近有效性。当前该领域正处于从“计算工具”向“统计推断框架”过渡的阶段：EOT 和 Sinkhorn 散度已被广泛应用于机器学习（生成模型、域适应）、计算生物学和计量经济学，但其渐近分布理论（中心极限定理、bootstrap 一致性）直到最近才被系统建立。本文是这一方向的最新进展之一。

发展脉络（history）

  1. 奠基工作：最优传输的熵正则化与 Sinkhorn 算法
  2. Cuturi (2013) 引入熵正则化，将最优传输问题转化为可高效求解的 Sinkhorn 算法，开启了“计算最优传输”时代。该工作主要关注计算效率，未涉及统计推断。

  3. Genevay et al. (2018) 提出 Sinkhorn 散度（Sinkhorn divergence），通过减去自耦合项消除熵正则化带来的偏差，使其成为满足三角不等式的真距离。该工作建立了 Sinkhorn 散度的理论性质，但未给出其样本版本的极限分布。

  4. 主要进展：EOT 映射的统计性质

  5. Mena & Weed (2019) 首次证明了经验 EOT 映射的 \(L^2\) 收敛率，但未涉及分布收敛。
  6. Genevay et al. (2019) 研究了 Sinkhorn 散度的渐近性质，证明了其作为分布距离的相合性，但未给出中心极限定理。

  7. Bigot et al. (2019) 在固定正则化参数下建立了经验 Sinkhorn 散度的渐近正态性，但依赖于较强的光滑性假设（如密度存在且光滑）。

  8. 当前 frontier：Hadamard 可微性与函数 delta 方法

  9. Goldfeld et al. (2022)（本文作者的前期工作）首次证明了 EOT 势函数关于边际分布的 Hadamard 可微性，并利用一阶函数 delta 方法得到了经验势函数的 CLT。但该工作仅处理了势函数，未涉及 EOT 映射和 Sinkhorn 散度。

  10. 本文 将 Hadamard 可微性分析推广到二阶，从而能够处理 Sinkhorn 散度（其极限分布涉及二阶项），并首次建立了 EOT 映射的 CLT 和 Sinkhorn 散度在原假设下的极限分布。同时，作为副产品获得了 bootstrap 一致性和渐近有效性。

  11. 本文的位置：本文是上述脉络的“自然下一步”——在已有的一阶可微性基础上，通过二阶分析填补了 Sinkhorn 散度推断的空白，并将 EOT 映射纳入统一的推断框架。

子线索聚类

  • 线索 A：EOT 映射的统计性质
    关注 EOT 映射作为边际分布函数的泛函的估计与推断。代表工作：Mena & Weed (2019)（收敛率）、本文（CLT + bootstrap）。
  • 线索 B：Sinkhorn 散度的推断
    关注 Sinkhorn 散度作为分布距离的假设检验与置信区间。代表工作：Genevay et al. (2019)（相合性）、Bigot et al. (2019)（光滑假设下的 CLT）、本文（一般假设下的 CLT + 独立性检验）。
  • 线索 C：Hadamard 可微性在最优传输中的应用
    将函数 delta 方法系统引入 EOT 领域。代表工作：Goldfeld et al. (2022)（一阶）、本文（二阶）。

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

  1. EOT 映射的渐近分布是什么？ 能否构造点wise 或 uniform 的置信带？
  2. Sinkhorn 散度在原假设下的极限分布是什么？ 能否用于独立性检验或两样本检验？
  3. bootstrap 是否一致？ 能否避免解析推导极限分布，直接使用 bootstrap 进行推断？
  4. 正则化参数 \(\varepsilon\) 如何影响推断？ 当 \(\varepsilon \to 0\) 时，EOT 是否退化为未正则化的 OT？极限分布是否连续？

⚠️ 作者的 framing

  • 作者把缺口 frame 成：已有工作（Goldfeld et al. 2022）只处理了 EOT 势函数的一阶可微性，无法处理 Sinkhorn 散度（需要二阶）和 EOT 映射（需要更强的可微性）。本文通过二阶 Hadamard 可微性填补了这一缺口，使得 Sinkhorn 散度的推断和 EOT 映射的 CLT 成为“显然的下一步”。
  • 被淡化或回避的竞争路线：
  • Bigot et al. (2019) 的密度光滑性假设被本文的“一般分布假设”替代，但本文的假设（如势函数的唯一性、边际分布的紧支撑）是否更弱或更强？作者未直接比较。
  • 未正则化的 OT 映射（如 Brenier 映射）的统计推断已有大量工作（如 Hütter & Rigollet 2021），但本文完全回避了与未正则化情形的比较——当 \(\varepsilon \to 0\) 时，本文的极限定理是否退化到未正则化情形？作者未讨论。
  • 什么明显该被引 / 该存在、却没出现在 intro 里？
  • Hütter & Rigollet (2021) 关于未正则化 OT 映射的 minimax 估计率——本文的 EOT 映射 CLT 是否能在 \(\varepsilon \to 0\) 时与之衔接？这是一个值得研究者去查的问题。
  • Deb et al. (2021) 关于 Sinkhorn 散度的 bootstrap 性质——本文的 bootstrap 一致性是否与之互补或冲突？

张力

未见明显对立引用。各工作主要在假设强度和应用场景上有所差异，而非结论矛盾。

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

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

  • 符号：
  • \(\mathcal{X}, \mathcal{Y} \subseteq \mathbb{R}^d\)：紧支撑的欧几里得空间（通常 \(\mathcal{X} = \mathcal{Y}\)）。
  • \(P, Q\)：\(\mathcal{X}\) 和 \(\mathcal{Y}\) 上的概率分布（边际分布）。
  • \(X_1, \dots, X_n \sim P\) 和 \(Y_1, \dots, Y_m \sim Q\)：独立同分布样本（可观测数据）。
  • \(c(x, y) = \|x - y\|^2 / 2\)：平方欧几里得代价函数（本文主要考虑二次代价，但结果可推广到更一般的代价）。
  • \(\varepsilon > 0\)：正则化参数（固定，不随样本量变化）。
  • \(\pi_\varepsilon(P, Q)\)：熵正则化最优传输计划，定义为：
    \[\pi_\varepsilon(P, Q) = \arg\min_{\pi \in \Pi(P, Q)} \left\{ \int c \, d\pi + \varepsilon \text{KL}(\pi \| P \otimes Q) \right\},\]
    其中 \(\Pi(P, Q)\) 是边际为 \(P, Q\) 的所有耦合。
  • \(T_\varepsilon(P, Q)\)：EOT 映射（当 \(\mathcal{X} = \mathcal{Y}\) 且代价为平方时，由 \(\pi_\varepsilon\) 的条件期望定义：\(T_\varepsilon(x) = \mathbb{E}_{Y \sim \pi_\varepsilon(\cdot | x)}[Y]\)）。
  • \(f_\varepsilon, g_\varepsilon\)：EOT 对偶势函数，满足：
    \[f_\varepsilon(x) = -\varepsilon \log \int_{\mathcal{Y}} \exp\left( \frac{g_\varepsilon(y) - c(x, y)}{\varepsilon} \right) dQ(y),\]
    \[g_\varepsilon(y) = -\varepsilon \log \int_{\mathcal{X}} \exp\left( \frac{f_\varepsilon(x) - c(x, y)}{\varepsilon} \right) dP(x).\]
    它们是 Sinkhorn 算法迭代的固定点。
  • \(S_\varepsilon(P, Q)\)：Sinkhorn 散度，定义为：
    \[S_\varepsilon(P, Q) = \text{EOT}_\varepsilon(P, Q) - \frac{1}{2} \text{EOT}_\varepsilon(P, P) - \frac{1}{2} \text{EOT}_\varepsilon(Q, Q),\]
    其中 \(\text{EOT}_\varepsilon(P, Q) = \int c \, d\pi_\varepsilon(P, Q) + \varepsilon \text{KL}(\pi_\varepsilon \| P \otimes Q)\) 是 EOT 代价。
  • \(\hat{P}_n, \hat{Q}_m\)：经验分布（基于样本）。
  • \(\hat{f}_{\varepsilon, n}, \hat{g}_{\varepsilon, m}\)：基于经验分布的对偶势函数（通过 Sinkhorn 算法计算）。
  • \(\hat{T}_{\varepsilon, n, m}\)：经验 EOT 映射。

  • \(\hat{S}_{\varepsilon, n, m}\)：经验 Sinkhorn 散度。

  • 模型：非参数模型——\(P\) 和 \(Q\) 是任意概率分布（满足紧支撑等正则条件），无参数化假设。研究者希望基于样本对 \(T_\varepsilon(P, Q)\)、\(f_\varepsilon\)、\(g_\varepsilon\) 和 \(S_\varepsilon(P, Q)\) 进行推断。

  • 可观测数据：研究者实际能观测到的是 \(n\) 个 i.i.d. 的 \(X_i\) 和 \(m\) 个 i.i.d. 的 \(Y_j\)。想要但观测不到的是：

  • 真实的 EOT 映射 \(T_\varepsilon(P, Q)\)（一个从 \(\mathcal{X}\) 到 \(\mathcal{Y}\) 的函数）。
  • 真实的对偶势函数 \(f_\varepsilon, g_\varepsilon\)。
  • 真实的 Sinkhorn 散度 \(S_\varepsilon(P, Q)\)（一个实数）。 这些量只能通过样本估计，且估计量的分布需要推导。

第二步：讲最小内核

最简特例：假设 \(\mathcal{X} = \mathcal{Y} = \mathbb{R}\)（一维），\(P\) 和 \(Q\) 是紧支撑上的连续分布，且代价为 \(c(x, y) = (x - y)^2 / 2\)。此时，EOT 映射 \(T_\varepsilon(P, Q)\) 退化为一个从 \(\mathbb{R}\) 到 \(\mathbb{R}\) 的函数，且已知其具有显式形式（通过 Schrödinger 桥问题）。

核心思路：本文的全部技术工作可以归结为证明 EOT 势函数 \((f_\varepsilon, g_\varepsilon)\) 作为边际分布 \((P, Q)\) 的泛函是 Hadamard 可微的，且可微性可以扩展到一阶和二阶。一旦有了这个可微性，函数 delta 方法就自动给出： - 一阶 delta 方法：\(\sqrt{n}(\hat{f}_{\varepsilon, n} - f_\varepsilon)\) 弱收敛到高斯过程（CLT for potentials）。 - 一阶 delta 方法 + 链式法则：\(\sqrt{n}(\hat{T}_{\varepsilon, n, m} - T_\varepsilon)\) 弱收敛到高斯过程（CLT for maps）。 - 二阶 delta 方法：\(n(\hat{S}_{\varepsilon, n, m} - S_\varepsilon(P, Q))\) 在原假设 \(P = Q\) 下收敛到卡方型分布（因为一阶项消失，二阶项主导）。

为什么这个特例能体现核心困难：即使在一维、二次代价的最简情形下，EOT 势函数 \((f_\varepsilon, g_\varepsilon)\) 作为 \((P, Q)\) 的泛函仍然是非线性的（涉及指数和对数积分），其 Hadamard 可微性并非显然。证明的关键在于利用 EOT 对偶问题的强凸性（由于熵正则化），将势函数表示为某个凸优化问题的唯一解，然后通过隐函数定理或扰动分析建立可微性。这个思路在一般维度下完全一样，只是技术细节更复杂（需要处理函数空间上的 Fréchet 导数）。

一句话总结本文的数学贡献：本文证明了“EOT 势函数 → 边际分布”这个映射是二阶 Hadamard 可微的，从而通过函数 delta 方法统一得到了 EOT 映射、势函数和 Sinkhorn 散度的极限定理。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：建立了熵正则化最优传输（EOT）映射、对偶势函数以及 Sinkhorn 散度的经验版本的中心极限定理（CLT）、bootstrap 一致性和渐近有效性。
  2. 核心工具 / 方法：对 EOT 势函数关于边际分布的一阶和二阶 Hadamard 可微性分析，结合一阶和二阶函数 delta 方法。
  3. 主要结论：① 经验 EOT 势函数和映射弱收敛到高斯过程；② 在原假设 \(P = Q\) 下，经验 Sinkhorn 散度乘以样本量收敛到卡方型分布（正确刻画了收敛阶）；③ Sinkhorn 独立性检验统计量的原假设极限分布被导出；④ bootstrap 一致性和渐近有效性成立。

关键设定与假设

  • 假设 1（紧支撑）：\(\mathcal{X}, \mathcal{Y} \subseteq \mathbb{R}^d\) 是紧集。这保证了势函数的有界性和指数项的良定义。
  • 假设 2（代价函数光滑性）：代价函数 \(c\) 是连续的（对二次代价自动满足）。本文主要考虑 \(c(x, y) = \|x - y\|^2 / 2\)，但结果可推广到更一般的代价。
  • 假设 3（势函数唯一性）：EOT 对偶问题的最优解 \((f_\varepsilon, g_\varepsilon)\) 在平移意义下唯一（即 \(f_\varepsilon + c, g_\varepsilon - c\) 也是解，但通过标准化如 \(\int f_\varepsilon dP = 0\) 可固定）。这要求边际分布 \(P, Q\) 的支撑足够“丰富”，使得 Sinkhorn 迭代收敛到唯一固定点。
  • 假设 4（样本量比例）：\(n, m \to \infty\) 且 \(n / (n+m) \to \lambda \in (0, 1)\)。这是两样本问题的标准假设。
  • 相比已有文献的放宽/强化：
  • 相比 Bigot et al. (2019) 要求密度存在且光滑，本文只要求分布有紧支撑（允许离散分布、奇异分布）。
  • 相比 Goldfeld et al. (2022) 只处理一阶可微性，本文推广到二阶，从而能处理 Sinkhorn 散度。

主要结果

  • 定理 3.1（EOT 势函数的 CLT）：在假设 1-4 下，\(\sqrt{n}(\hat{f}_{\varepsilon, n} - f_\varepsilon)\) 和 \(\sqrt{m}(\hat{g}_{\varepsilon, m} - g_\varepsilon)\) 在 \(L^2(P)\) 和 \(L^2(Q)\) 中弱收敛到均值为零的高斯过程。直觉：由于势函数是边际分布的 Hadamard 可微泛函，经验势函数的波动由经验过程的波动通过导数映射传递。必要条件：正则化参数 \(\varepsilon > 0\) 固定（不随样本量衰减）。
  • 定理 3.2（EOT 映射的 CLT）：在相同假设下，\(\sqrt{n}(\hat{T}_{\varepsilon, n, m} - T_\varepsilon)\) 在 \(L^2(P)\) 中弱收敛到高斯过程。技术难点：EOT 映射是势函数的函数（通过条件期望），因此需要链式法则和势函数 CLT 的组合。解决：利用 EOT 映射关于势函数的显式表达式（通过 Schrödinger 桥）和势函数 CLT。
  • 定理 4.1（Sinkhorn 散度的极限分布）：在原假设 \(P = Q\) 下，\(n \hat{S}_{\varepsilon, n, n} \Rightarrow \sum_{k=1}^\infty \lambda_k Z_k^2\)，其中 \(Z_k\) 是独立标准正态，\(\lambda_k\) 是某个紧算子的特征值。直觉：当 \(P = Q\) 时，Sinkhorn 散度的一阶项消失（因为 \(S_\varepsilon(P, P) = 0\)），二阶项主导，因此收敛阶为 \(n\) 而非 \(\sqrt{n}\)。正确收敛阶：这是本文的关键贡献——之前的工作（如 Bigot et al. 2019）只得到了 \(\sqrt{n}\) 收敛（因为未正确识别一阶项消失），本文首次刻画了正确的 \(n\) 阶。
  • 定理 4.2（Sinkhorn 独立性检验）：对于联合分布 \(P_{XY}\) 和乘积边际 \(P_X \otimes P_Y\)，检验统计量 \(n \hat{S}_{\varepsilon, n}(P_{XY}, P_X \otimes P_Y)\) 在原假设（独立性）下收敛到卡方型分布。应用：可用于检验两个随机变量是否独立，作为经典独立性检验（如距离相关性）的替代。
  • 定理 5.1（Bootstrap 一致性）：经验 EOT 映射、势函数和 Sinkhorn 散度的 bootstrap 版本（基于重抽样）弱收敛到与原始极限分布相同的分布。意义：无需解析推导极限分布的显式形式，可直接使用 bootstrap 构造置信区间和进行假设检验。
  • 定理 5.2（渐近有效性）：经验 EOT 映射和势函数是渐近有效的（即达到半参数效率界）。意义：在非参数模型中，没有其他估计量能在渐近方差意义上比本文的估计量更好。

证明路线与技术技巧

整体路线（以 Sinkhorn 散度的极限分布为例）：

  1. 步骤 1：建立 EOT 势函数的二阶 Hadamard 可微性。将 \((f_\varepsilon, g_\varepsilon)\) 视为 \((P, Q)\) 的泛函 \(\Phi(P, Q)\)。证明 \(\Phi\) 在 \((P, Q)\) 处是二阶 Hadamard 可微的，即存在线性映射 \(\Phi'\) 和双线性映射 \(\Phi''\)，使得：

    \[\Phi(P + h, Q + k) = \Phi(P, Q) + \Phi'(h, k) + \frac{1}{2} \Phi''(h, k) + o(\|h\|^2 + \|k\|^2).\]
    关键技巧：利用 EOT 对偶问题的强凸性，将势函数表示为某个凸优化问题的唯一解，然后通过隐函数定理的泛函版本（或扰动分析）计算导数。具体地，对偶问题的目标函数是严格凸的（由于熵正则化），因此最优解关于扰动的变化可以通过求解一个线性化方程得到。

  2. 步骤 2：将二阶 delta 方法应用于 Sinkhorn 散度。Sinkhorn 散度 \(S_\varepsilon(P, Q)\) 可以表示为势函数的函数：\(S_\varepsilon(P, Q) = \Psi(\Phi(P, Q))\)，其中 \(\Psi\) 是某个已知的二次型。利用链式法则，\(S_\varepsilon\) 作为 \((P, Q)\) 的泛函也是二阶 Hadamard 可微的。

  3. 步骤 3：在原假设 \(P = Q\) 下，一阶项消失。当 \(P = Q\) 时，\(S_\varepsilon(P, P) = 0\)，且其一阶导数也为零（因为 Sinkhorn 散度在 \(P = Q\) 处达到最小值）。因此，经验 Sinkhorn 散度的波动由二阶项主导：

    \[n \hat{S}_{\varepsilon, n, n} = \frac{1}{2} \Phi''(\sqrt{n}(\hat{P}_n - P), \sqrt{n}(\hat{Q}_n - P)) + o_P(1).\]

  4. 步骤 4：识别极限分布。二阶项 \(\Phi''\) 是经验过程的二次型。由于经验过程弱收敛到布朗桥，该二次型收敛到高斯过程的二次型，即卡方型分布 \(\sum \lambda_k Z_k^2\)。关键跳跃点：需要证明 \(\Phi''\) 是紧算子，以保证特征值 \(\lambda_k\) 可求和且极限分布良定义。这依赖于 EOT 问题的光滑性（指数核的平滑效应）。

技术技巧点名： - Hadamard 可微性：核心工具，用于将经验过程的收敛性“传递”到 EOT 泛函。 - 函数 delta 方法：一阶用于势函数和映射，二阶用于 Sinkhorn 散度。 - 隐函数定理的泛函版本：用于计算 EOT 势函数关于边际分布的导数。 - 紧算子谱分解：用于刻画 Sinkhorn 散度极限分布的卡方型形式。 - Bootstrap 一致性：通过 Hadamard 可微性自动获得（因为 bootstrap 对经验过程一致）。

真实例子与应用

本文为纯理论论文，无真实数据例子或模拟实验。 所有结果均为渐近理论（CLT、bootstrap 一致性、渐近有效性），未提供有限样本模拟或实际数据应用。作者在结论部分提到“模拟实验和实际数据应用留待未来工作”。

🔎 结论是否比证明窄

  • 定理 4.1（Sinkhorn 散度极限分布） 的证明依赖于原假设 \(P = Q\)。作者在定理陈述中明确写了“under the null \(P = Q\)”，但在结论部分暗示该结果可用于一般的两样本检验（即 \(P \neq Q\) 时的检验功效）。严格来说，本文只给出了原假设下的极限分布，未证明备择假设下的行为（如检验的一致性）。 这是一个值得注意的窄化：读者不应误以为本文提供了完整的检验理论。
  • 定理 3.2（EOT 映射 CLT） 的证明要求 \(\mathcal{X} = \mathcal{Y}\) 且代价为平方欧几里得距离。作者在假设中明确写了这一点，但在讨论中暗示可推广到更一般的代价和不同空间。推广到一般代价需要重新验证 Hadamard 可微性，并非自动成立。
  • Bootstrap 一致性（定理 5.1） 的证明依赖于 Hadamard 可微性，但 bootstrap 的有限样本表现（如覆盖率的准确性）未在模拟中验证。作者仅提供了理论保证，未讨论 bootstrap 的收敛速度或高阶校正。

四、开放问题

  1. 当正则化参数 \(\varepsilon \to 0\) 时，极限定理是否退化到未正则化 OT 的情形？
    扎根于：本文所有结果均假设 \(\varepsilon > 0\) 固定。作者在结论部分提到“研究 \(\varepsilon \to 0\) 时的渐近行为是重要的未来工作”。当 \(\varepsilon\) 很小时，EOT 映射接近未正则化的 Brenier 映射，但本文的 CLT 可能不再成立（因为 Hadamard 可微性在 \(\varepsilon = 0\) 处失效）。这是一个高价值问题：能否建立“小正则化”下的统一极限理论？

  2. Sinkhorn 散度在备择假设 \(P \neq Q\) 下的极限分布是什么？
    扎根于：定理 4.1 只处理了原假设。对于两样本检验，需要知道在 \(P \neq Q\) 下检验统计量的分布（或至少检验的一致性）。作者未讨论这一点。一个自然的后续工作是建立 Sinkhorn 散度在固定备择假设下的 CLT（此时一阶项非零，收敛阶为 \(\sqrt{n}\)）。

  3. EOT 映射的 uniform CLT（在函数空间上的弱收敛）能否建立？
    扎根于：定理 3.2 给出了 \(L^2(P)\) 中的弱收敛。对于构造 uniform 置信带（如 Kolmogorov-Smirnov 型），需要 \(L^\infty\) 或 Hölder 空间中的 CLT。这要求更强的可微性（如 Hadamard 可微性在更强范数下成立），目前尚未被研究。

  4. 高维情形下的极限定理？
    扎根于：本文假设 \(\mathcal{X}, \mathcal{Y} \subseteq \mathbb{R}^d\) 是紧集，但 \(d\) 固定。当 \(d\) 随样本量增长时（高维最优传输），EOT 映射的统计性质如何？此时 Sinkhorn 算法本身的计算复杂度（涉及 \(O(n^2)\) 的核矩阵）成为瓶颈，而本文的渐近理论（基于 \(n \to \infty\)、\(d\) 固定）不再适用。这是一个开放且困难的问题，可能涉及随机矩阵理论和计算-统计权衡。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论