最优输运方案的定量稳定性和误差估计
本文介绍了一种计算两个测度之间 L2 最优传输图的数值算法,其中一个测度源自由分段线性函数(由四面体网格支持)定义的密度 rho,而另一个测度则是 Dirac 质量之和。作者提出了一个实用的算法来计算分段线性密度与 Dirac 质量总和之间的最优传输图。
Sep, 2014
该论文研究了一种通过优化传输映射将概率测度集嵌入希尔伯特空间的方法,并证明了当参考概率密度在一个凸集上均匀分布时,该嵌入具有 (bi-) H"older 连续性,同时可等价解释为对于优化传输映射的维度无关的 H"older 稳定性结果。这一方法使得一般的监督学习和无监督学习算法可以直接应用于测度数据上。
Oct, 2019
本文提出更快的算法来近似计算两个离散概率分布之间的最优传输距离(如移动距离),同时提供对其的简要介绍和优化,通过将最优传输归约为规范化优化问题,该问题可以在近似线性时间内解决,处理了 linear programs 等问题。
Oct, 2018
本文对通过重心投影定义的常规插值估计器的收敛速度进行了全面的分析,利用这种稳定度量来提高优化运输地图的估计器的速度,减轻维数诅咒,并加速 Wasserstein 距离的收敛速度。
Jul, 2021
本文提出了一个基于离散最优输运问题的简单子抽样方案,用于快速随机近似计算最优输运距离。该方案针对完全数据的随机子集操作,可使用任何精确算法作为黑盒后端,包括最先进的求解器和熵惩罚版本。我们给出了其非渐进偏差范围,以针对更高的精度或更短的计算时间进行简化。实验证明,该子抽样方案可以在计算时间大大降低的情况下,获得比精确方法更好的近似效果。
Feb, 2018
本文提出了一个新颖的两步方法来解决基本问题,即从一个分布学习到另一个分布的最优映射,首先我们学习一个最优传输(OT)方案,其次我们估计 Monge 映射作为一个深度神经网络,演示了我们的建议方法在域适应和生成建模方面的应用。
Nov, 2017
研究了 $d>2$ 离散测度的最优输运问题,提出了有熵正则化项的线性规划方案,并引入了 Sinkhorn 扩展算法,并给出了严格凸函数部分最小化算法的变形,得到其收敛速度的几何估计。
May, 2020
本文主要讨论了在源测度和目标测度均为次高斯测度的情况下,估计具有平方欧氏距离成本的熵正则化最优传输(EOT)映射的问题,并指出了在目标测度具有紧支集或强对数凹性时,即使采用了最近提出的样本内估计器,期望均方 $L^2$ 误差仅以至少 $O (n^{-1/3})$ 的速率衰减,而对于一般次高斯情况,期望 $L^1$ 误差以至少 $O (n^{-1/6})$ 的速率衰减,并且这些结果在正则化参数上具有多项式依赖性。由于这些结果消除了对紧支集的要求,因此尽管与源测度和目标测度均为紧支集(平方 $L^2$ 误差以速率 $O (n^{-1})$ 收敛)或源测度为次高斯而目标测度为紧支集(平方 $L^2$ 误差以速率 $O (n^{-1/2})$ 收敛)的已知结果相比还不够优化,但它们具有重要意义。证明技巧利用了偏差 - 方差分解,其中方差通过标准的集中度结果进行控制,而偏差则通过 T1 - 传输不等式以及在次高斯假设下估计 EOT 成本的样本复杂性结果来处理。实验结果显示了对方差项控制的松弛性,并最后提出了几个开放性问题。
Nov, 2023
通过优化传输度量,在嵌入 Hilbert 空间的流形上估计一种衡量方法,并将量化优化和学习理论联系起来,为无监督学习中经典算法(k-means)的性能提供新的概率界限。在分析的过程中,我们得出了新的下界和概率上界,这些上下界适用于广泛的测度范围。
Sep, 2012