跳转至

Convergence of empirical optimal transport in unbounded settings

作者: Thomas Staudt, Shayan Hundrieser
来源: Bernoulli
主题: 非参数 / 半参数
相关性: 8/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么： 经验最优传输代价的收敛速率研究，核心统计问题是：给定两个概率测度 \(\mu, \nu\)，基于 \(n\) 个独立同分布样本构造的经验测度 \(\hat{\mu}_n, \hat{\nu}_n\)，其经验 OT 代价 \(\mathcal{T}_c(\hat{\mu}_n, \hat{\nu}_n)\) 向总体 OT 代价 \(\mathcal{T}_c(\mu, \nu)\) 收敛的速率是多少？该方向当前在紧支撑设定下已形成近乎完备的 minimax 理论，但在无界设定下，由于尾部质量逃逸与成本函数无界，收敛率的刻画仍存在大量假设冗余与缺口。

发展脉络： - 奠基工作：Dudley (1969) 建立了紧空间上经验测度在 Wasserstein 距离下的收敛率上界 \(O(n^{-1/d})\)；Ajtai-Komlós-Tusnády (1984) 给出了 \(d=2\) 时二部匹配的 \(O(\sqrt{\log n/n})\) 下界，确立了紧空间上收敛率的基准。 - 主要进展（紧空间完备化）：Boissard & Le Gouic (2014) 与 Weed & Bach (2019) 将紧空间上的收敛率推广至一般度量空间，并给出了依赖于测度复杂度（如覆盖数、Minkowski 维数）的渐近与有限样本界；Fournier & Guillin (2015) 在欧氏空间上基于耦合技术给出了非渐近界，但要求测度具有亚高斯或指数矩。 - 当前 frontier（低复杂度自适应与无界设定）：Manole & Niles-Weed (2021) 证明了对光滑成本函数，经验 OT 代价的收敛率可从 \(n^{-1/d}\) 加速至 \(n^{-2/d}\)；Hundrieser et al. (2022) 发现了“低复杂度自适应”现象——经验 OT 代价的收敛率由两个测度中复杂度较低的那个决定；对于半离散情形，del Barrio et al. (2023) 证明了参数速率 \(n^{-1/2}\) 的中心极限定理。然而，这些精细结果大多局限于紧支撑或强矩条件设定。 - 本文的位置：本文旨在将紧空间上已确立的收敛率与低复杂度自适应现象，在仅假设测度具有有限矩的条件下，迁移至无界设定，且速率损失仅限于任意小的 \(\epsilon > 0\)。

子线索聚类： 1. 紧空间收敛率与复杂度依赖：聚焦于测度支撑有界时，收敛率如何依赖于空间维数与测度的内在复杂度（如 Weed & Bach 2019, Manole & Niles-Weed 2021, Hundrieser et al. 2022）。 2. 无界/欧氏空间收敛率与矩条件：聚焦于测度支撑无界时，如何通过矩条件控制尾部误差，以获得非渐近界（如 Fournier & Guillin 2015, Lei 2020, Deb et al. 2021）。 3. OT 代价的渐近分布与半参数推断：聚焦于特定结构（如半离散、光滑密度）下 OT 代价的中心极限定理与推断（如 Sommerfeld & Munk 2016, del Barrio et al. 2023）。

核心追问与已知瓶颈： 1. 无界设定下收敛率的紧致性：紧空间上的收敛率界在无界设定下是否依然成立？已知瓶颈是，Fournier & Guillin (2015) 等要求亚高斯或指数矩才能得到 \(n^{-p/d}\) 的界，矩条件远强于必要。 2. 低复杂度自适应的无界推广：紧空间上 OT 代价自适应于低复杂度测度的现象，在无界设定下是否被破坏？已知瓶颈是，尾部质量可能导致额外的对数因子或速率退化。 3. 光滑成本与半离散结构的速率加速：光滑成本带来的 \(n^{-2/d}\) 加速与半离散带来的 \(n^{-1/2}\) 加速，在无界设定下是否需要更强的矩条件？

⚠️ 作者的 framing： - 作者将缺口 frame 为：“紧空间上的理论已完备，但无界设定下已有结果要求过强的矩条件（如亚高斯），本文仅用有限矩条件即可恢复紧空间上的速率（仅损失 \(\epsilon\)）”。这使得本文的“分解-截断”策略成为显然的下一步：将无界测度截断为紧支撑部分与尾部部分，分别用紧空间理论处理前者、用矩条件控制后者。 - 被淡化或回避的竞争路线：基于耦合技术（如 Fournier & Guillin 2015）的直接非渐近界构造，作者虽引用但未深入对比其矩条件冗余的根源；基于 Sinkhorn 正则化的计算-统计权衡路线（如 Chizat et al. 2020, Niles-Weed & Rigollet 2022）完全未在 intro 中出现。 - 明显该被引却未出现的：关于统计-计算权衡的文献（Niles-Weed & Rigollet 2019 提出了 Spiked Transport Model 并暗示了计算间隙），以及高维 OT 估计的结构假设文献（如 Forrow et al. 2019 的低秩耦合），这些直接关联 OT 估计的 minimax 界与计算可行性，但作者未提及——这值得研究者去查：作者是否刻意回避了计算可行性对收敛率界的影响？

张力： 未见明显对立引用。但存在隐含张力：Fournier & Guillin (2015) 通过耦合技术要求亚高斯矩才能得到 \(n^{-p/d}\) 的界，而本文声称仅需有限矩即可得到近乎相同的界（损失 \(\epsilon\)）。这两者在矩条件上的差异是实质性的，但作者未明确解释为何耦合技术无法在弱矩下达到相同效果，而截断策略可以——这暗示了两种技术路线在处理尾部误差时的内在差异，值得研究者深挖。

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

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

  • 符号：
  • \(\mu, \nu\)：两个概率测度（总体测度），定义在波兰空间 \((\mathcal{X}, \mathcal{A})\) 与 \((\mathcal{Y}, \mathcal{B})\) 上。
  • \(c: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}_{\geq 0}\)：成本函数（cost function），衡量从 \(x\) 运输到 \(y\) 的代价。
  • \(\mathcal{T}_c(\mu, \nu)\)：总体 OT 代价（estimand），定义为 \(\inf_{\pi \in \Pi(\mu, \nu)} \int c \, d\pi\)，其中 \(\Pi(\mu, \nu)\) 是所有以 \(\mu, \nu\)为边缘的联合测度集合。
  • \(X_1, \dots, X_n \sim \mu\)，\(Y_1, \dots, Y_n \sim \nu\)：独立同分布样本（随机变量）。
  • \(\hat{\mu}_n = \frac{1}{n} \sum_{i=1}^n \delta_{X_i}\)，\(\hat{\nu}_n = \frac{1}{n} \sum_{i=1}^n \delta_{Y_i}\)：经验测度（可观测数据）。
  • \(\hat{\mathcal{T}}_c = \mathcal{T}_c(\hat{\mu}_n, \hat{\nu}_n)\)：经验 OT 代价（基于样本的 plug-in 估计量）。
  • \(d\)：测度的内在维数或 Minkowski 维数（指标）。
  • \(p\)：成本函数的增长阶数（指标），即 \(c(x,y) \leq C(1 + \|x\|^p + \|y\|^p)\)。
  • \(\epsilon > 0\)：任意小的常数，用于刻画收敛率损失。

  • \(r\)：截断半径（参数），用于将测度分为紧支撑部分与尾部部分。

  • 模型： 数据生成机制为：从总体测度 \(\mu, \nu\) 中独立抽取 \(n\) 个样本，形成经验测度 \(\hat{\mu}_n, \hat{\nu}_n\)。成本函数 \(c\) 满足增长条件 \(c(x,y) \leq C(1 + \|x\|^p + \|y\|^p)\)。总体测度 \(\mu, \nu\) 假设具有有限 \(s\) 阶矩（\(s > p\)）。目标是估计总体 OT 代价 \(\mathcal{T}_c(\mu, \nu)\)。

  • 可观测数据： 研究者实际能观测到的是样本 \(X_1, \dots, X_n\) 与 \(Y_1, \dots, Y_n\)，构成经验测度 \(\hat{\mu}_n, \hat{\nu}_n\)。总体测度 \(\mu, \nu\) 与总体 OT 代价 \(\mathcal{T}_c(\mu, \nu)\) 是不可观测的 estimand，只能通过经验 OT 代价 \(\hat{\mathcal{T}}_c\) 与假设（矩条件、成本增长条件）去识别与估计。

第二步：最小内核——紧支撑截断与尾部误差分解

本文的核心数学困难在于：无界空间上，成本函数 \(c\) 无界，导致经验测度的尾部质量可能产生巨大的运输代价，使得紧空间上的收敛率界无法直接套用。最小内核是：如何通过截断将无界问题分解为紧支撑部分与尾部部分，并分别控制其误差？

考虑最简特例：欧氏空间 \(\mathbb{R}^d\) 上的 \(p\)-Wasserstein 距离（\(c(x,y) = \|x-y\|^p\)），单样本情形（\(\hat{\mu}_n\) 经验测度向 \(\mu\) 收敛，\(\nu\) 固定且已知）。

  1. 截断分解：选取截断半径 \(r\)，将 \(\mu\) 分为紧支撑部分 \(\mu_r = \mu|_{\mathcal{X}_r}\)（限制在半径 \(r\) 的球内，重新归一化）与尾部部分 \(\mu - \mu_r^{\text{mass}}\)（球外的质量）。同理对 \(\hat{\mu}_n\) 进行截断得到 \(\hat{\mu}_{n,r}\)。
  2. 紧支撑部分误差：在紧支撑 \(\mathcal{X}_r\) 上，\(\hat{\mu}_{n,r}\) 向 \(\mu_r\) 的收敛率由紧空间理论决定，为 \(O(n^{-p/d})\)（若 \(\mu_r\) 有绝对连续密度）或 \(O(n^{-1/2})\)（若 \(\mu_r\) 为半离散）。
  3. 尾部误差控制：尾部质量 \(\mu(\mathcal{X} \setminus \mathcal{X}_r)\) 随 \(r \to \infty\) 衰减。关键在于：如何选择 \(r\) 使得尾部误差不超过紧支撑部分的收敛率？利用矩条件 \(\int \|x\|^s \, d\mu(x) < \infty\)（\(s > p\)），尾部质量满足 \(\mu(\mathcal{X} \setminus \mathcal{X}_r) \leq C r^{-s}\)，尾部运输代价满足 \(\int_{\mathcal{X} \setminus \mathcal{X}_r} \|x\|^p \, d\mu(x) \leq C r^{-(s-p)}\)。
  4. 平衡截断半径：为使尾部误差 \(O(r^{-(s-p)})\) 与紧支撑收敛率 \(O(n^{-p/d})\) 同阶，需选取 \(r = n^{p/(d(s-p))}\)。此时，总误差为 \(O(n^{-p/d} + n^{-p(s-p)/(d(s-p))}) = O(n^{-p/d + \epsilon})\)，其中 \(\epsilon = p^2/(d(s-p))\) 可通过增大 \(s\)（更强的矩条件）使之任意小。

这个特例揭示了本文的核心思路：截断半径 \(r\) 的选择是紧支撑收敛率与尾部误差的平衡点，矩条件 \(s > p\) 决定了尾部衰减速度，从而决定了收敛率损失 \(\epsilon\) 的大小。一般情形的证明只是这个分解的“加壳”：处理两样本情形、一般成本函数、低复杂度自适应、以及半凹成本下的 \(n^{-2/d}\) 加速。

三、这篇论文做了什么

三句话： ①研究了无界设定下经验 OT 代价向总体值的收敛速率问题； ②核心方法是基于截断的分解策略，将无界测度分为紧支撑部分与尾部部分，分别用紧空间理论与矩条件控制； ③主要结论是在有限矩条件下，无界设定下的收敛率仅比紧空间设定损失任意小的 \(\epsilon > 0\)，且低复杂度自适应与光滑成本加速现象依然成立。

关键设定与假设： - Assumption (Cost)：成本函数 \(c\) 满足 \(c(x,y) \leq C(1 + d(x,x_0)^p + d(y,y_0)^p)\)，其中 \(p \geq 1\)，\(x_0, y_0\) 是参考点。统计含义：成本函数的增长被 \(p\) 阶多项式控制，避免指数增长导致的尾部爆炸。 - Assumption (Moment)：\(\mu\) 与 \(\nu\) 具有有限 \(s\) 阶矩，即 \(\int d(x,x_0)^s \, d\mu(x) < \infty\)，\(\int d(y,y_0)^s \, d\nu(y) < \infty\)，且 \(s > p\)。统计含义：测度的尾部衰减足够快，使得截断后的尾部误差可控。相比 Fournier & Guillin (2015) 要求的亚高斯矩（\(s = \infty\) 实质上），本文将矩条件弱化至 \(s > p\)，且声称这是 sharp up to \(\epsilon\)。 - Assumption (BC)：紧支撑截断后的测度 \(\mu_r, \nu_r\) 满足紧空间上的收敛率假设（如绝对连续密度、半离散等）。统计含义：将紧空间上的已知结果直接套用至截断部分。 - 低复杂度自适应设定：若 \(\mu\) 支撑在 \(d\) 维流形上而 \(\nu\) 任意，收敛率由 \(\mu\) 的维数 \(d\) 决定。本文将此现象推广至无界设定。

主要结果： 1. Theorem 1（主定理：无界设定下的收敛率界）：在 Assumption (Cost) 与 (Moment) 下，若紧空间上的收敛率为 \(O(n^{-\alpha})\)（\(\alpha \in (0,1]\)），则无界设定下的收敛率为 \(O(n^{-\alpha + \epsilon})\)，其中 \(\epsilon = p^2/(d(s-p))\) 可通过增大 \(s\) 使之任意小。直觉：截断半径 \(r\) 的选择平衡了紧支撑误差与尾部误差，矩条件 \(s\) 越强，尾部衰减越快，\(\epsilon\) 越小。必要条件：\(s > p\)，否则尾部误差无法被控制。技术难点：如何在不引入对数因子的情况下，将尾部误差与紧支撑误差加和，且保持紧空间上的速率结构。 2. Corollary 1（低复杂度自适应的无界推广）：若 \(\mu\) 支撑在 \(d\) 维流形上，\(\nu\) 任意（可能高维或无界），在 Lipschitz 成本下，经验 OT 代价的收敛率为 \(O(n^{-1/d + \epsilon})\)；在半凹成本下，收敛率为 \(O(n^{-2/d + \epsilon})\)。直觉：低复杂度自适应现象在无界设定下依然成立，因为截断只影响尾部，不影响流形的内在维数。 3. Proposition 1（半离散情形的参数速率）：若 \(\mu\) 为半离散测度（支撑在有限点上），\(\nu\) 任意，在有限矩条件下，收敛率为 \(O(n^{-1/2 + \epsilon})\)。直觉：半离散结构使得 OT 代价的估计退化为有限维参数估计，截断尾部不改变这一结构。

证明路线与技术技巧： - 整体路线： 1. 截断构造：选取截断半径 \(r = n^{p/(d(s-p))}\)，将 \(\mu, \nu\) 分为紧支撑部分 \(\mu_r, \nu_r\) 与尾部部分 \(\mu - \mu_r^{\text{mass}}, \nu - \nu_r^{\text{mass}}\)。 2. OT 代价分解：将总体 OT 代价 \(\mathcal{T}_c(\mu, \nu)\) 分解为紧支撑部分 \(\mathcal{T}_c(\mu_r, \nu_r)\) 与尾部运输代价（将尾部质量运输至紧支撑部分或参考点）。 3. 紧支撑部分收敛率：套用紧空间上的已知收敛率界（如 Weed & Bach 2019, Hundrieser et al. 2022），得到 \(\mathcal{T}_c(\hat{\mu}_{n,r}, \hat{\nu}_{n,r})\) 向 \(\mathcal{T}_c(\mu_r, \nu_r)\) 的收敛率为 \(O(n^{-\alpha})\)。 4. 尾部误差控制：利用矩条件，证明尾部运输代价的误差为 \(O(r^{-(s-p)}) = O(n^{-p(s-p)/(d(s-p))})\)。 5. 加和与平衡：将紧支撑误差与尾部误差加和，通过 \(r\) 的选择使两者同阶，得到总误差 \(O(n^{-\alpha + \epsilon})\)。 - 关键跳跃点： - Lemma 3（截断后的 OT 代价分解不等式）：\(\mathcal{T}_c(\mu, \nu) \leq \mathcal{T}_c(\mu_r, \nu_r) + \text{尾部误差}\)，且该不等式的常数不依赖于 \(r\)。难点在于：如何在不引入额外对数因子的情况下，将尾部质量的运输代价用矩条件控制。作者通过构造一个“参考运输计划”（将尾部质量运输至参考点 \(x_0, y_0\)），绕过了直接估计尾部质量之间最优运输的困难。 - Lemma 5（经验测度的截断误差控制）：\(\mathbb{E}[\mathcal{T}_c(\hat{\mu}_n, \hat{\mu}_{n,r})] \leq C r^{-(s-p)}\)。难点在于：经验测度的尾部质量是随机的，可能偏离总体尾部质量。作者利用经验过程理论，证明经验尾部质量的矩偏差可控。 - 技术技巧点名： - 截断-分解策略：用在步骤 1-2，将无界问题化为紧支撑+尾部。 - 矩条件控制尾部：用在步骤 4，通过 Markov 不等式与矩积分，将尾部运输代价用 \(r^{-(s-p)}\) 控制。 - 经验过程理论：用在 Lemma 5，控制经验测度截断后的随机偏差。 - 紧空间 OT 收敛率套用：用在步骤 3，直接引用 Hundrieser et al. (2022) 与 Manole & Niles-Weed (2021) 的结果，避免重新证明。 - 参考运输计划构造：用在 Lemma 3，绕过尾部质量之间直接最优运输的估计困难。

真实例子与应用： 本文为纯理论论文，无实证例子。但作者在 intro 中提及了 OT 在生物学（Schiebinger et al. 2019 的单细胞 RNA 序列轨迹推断）、经济学（Galichon 2016）与机器学习（Gulrajani et al. 2017 的 Wasserstein GAN）中的应用，作为理论结果的动机。

🔎 结论是否比证明窄： - 作者声称收敛率“sharp up to \(\epsilon > 0\)”，但证明中 \(\epsilon\) 的具体表达式为 \(\epsilon = p^2/(d(s-p))\)，这意味着要使 \(\epsilon\) 任意小，需 \(s \gg p\)（矩阶数远大于成本增长阶数）。然而，作者在 intro 中将此 frame 为“仅需有限矩条件”，这实质上要求 \(s\) 足够大而非仅仅 \(s > p\)。这是一个泛泛 claim 比证明窄的地方：证明要求 \(s\) 依赖于 \(\epsilon\) 与 \(d\)，而 intro 暗示 \(s > p\) 即可。 - Corollary 1 声称低复杂度自适应在无界设定下“依然成立”，但证明中要求 \(\nu\) 的矩条件 \(s > p\) 且 \(s\) 依赖于 \(\epsilon\)，这意味着自适应现象在弱矩下可能被尾部误差破坏——作者未明确讨论这一条件依赖。

四、开放问题（点到为止，扎根具体语句）

  1. 矩条件的紧致性：本文要求 \(s > p\) 且 \(s\) 依赖于 \(\epsilon\)，但收敛率在 \(s = p\) 时是否退化至 \(O(n^{-\alpha} \log n)\) 或更慢？扎根于 Theorem 1 的必要条件陈述：“\(s > p\) is required for the tail error to be controlled”。
  2. 对数因子的消除：紧空间上 \(d=2\) 时收敛率为 \(O(\sqrt{\log n/n})\)（AKT 定理），本文的无界推广是否引入额外对数因子？扎根于 intro 对 AKT 定理的讨论：“it remains an open question whether (2.1) is sharp for \(d=2\)”。
  3. 计算-统计权衡：本文的收敛率界是针对 plug-in 估计量的，但在高维无界设定下，是否存在统计-计算间隙（如 Niles-Weed & Rigollet 2019 暗示的）？扎根于 intro 未提及的 Niles-Weed & Rigollet (2019) 的 Spiked Transport Model——这值得研究者去查：本文的界是否在多项式时间可达到？
  4. 半参数推断的可行性：本文给出了收敛率界，但未给出渐近分布。在半离散或光滑成本的无界设定下，OT 代价的中心极限定理是否成立？扎根于 intro 对 del Barrio et al. (2023) 的引用：“they prove the parametric \(n^{-1/2}\)-rate if \(\nu\) possesses a finite second moment”——本文的 \(n^{-1/2+\epsilon}\) 界是否可改进至 \(n^{-1/2}\) 并建立 CLT？

Maintained by 陈星宇 · Homepage · Source on GitHub

评论