Jun, 2019

一种直接的 $ ilde {O}(1/ε)$ 迭代并行算法，用于最优输运

PDF
TL;DR本文介绍一种基于原始对偶外推方法的平行一阶算法，通过计算最优传输（包括基于 Wasserstein 距离的计算）来解决机器学习和统计学中常见的问题，具有较强的实际应用价值，并实验验证了优异的性能。
optimal transportationwasserstein distanceprimal-dual extragradient methodparallel computingdimensionality independence
发现论文，激发创造
  • 求解最优输运问题的最优运行时间

    本文提出更快的算法来近似计算两个离散概率分布之间的最优传输距离（如移动距离），同时提供对其的简要介绍和优化，通过将最优传输归约为规范化优化问题，该问题可以在近似线性时间内解决，处理了 linear programs 等问题。

    Oct, 2018

  • 计算最优传输：加速梯度下降比 Sinkhorn 算法更好的复杂度

    本研究分析了逼近两个离散分布之间的一般最优运输（OT）距离的两种算法，并证明了复杂度界限，其中一种基于 Sinkhorn 算法，另一种基于 Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) 算法。与先前的最优界限相比，我们的算法具有更好的复杂度界限，更好地依赖于 ε，同时可用于各种正则项。

    Feb, 2018

  • 可扩展的最近邻搜索用于最优输运

    这篇论文介绍一种快速、准确的 Wasserstein-1 距离近邻搜索算法 Flowtree，通过实验表明它比之前的最先进算法快 7.4 倍。

    Oct, 2019

  • 最优输运的图论加法逼近

    本文提出了一种基于 Gabow 和 Tarjan 的图算法的新颖分析，并提供了一个简单的贪婪式迭代算法，其执行时间为 O (n^2*C/δ + nC^2/δ^2)，用于求解概率分布的最优运输问题，在数值不稳定的情况下具有竞争力的执行时间。

    May, 2019

  • 通过 Sinkhorn 迭代的近线性时间逼近算法优化输运问题

    本文介绍了 Cuturi 的 Sinkhorn 距离的新分析方法，表明这种算法能够近似地在线性时间内计算出一般上的最优输运距离，同时提出了相应的一种新的贪心坐标下降算法 Greenkhorn，并通过数值模拟表明 Greenkhorn 在实践中比经典的 Sinkhorn 算法显著优越。

    May, 2017

  • 近线性时间内逼近二次传输度量

    该研究提出了一种基于熵正则化、近似 Sinkhorn 缩放和高斯核矩阵低秩逼近的算法，用于计算两个点云或离散分布之间的二次输运度量（也称为 2-Wasserstein 距离或均方根距离），其复杂度为 O (n)。

    Oct, 2018

  • 快速求解最优输运问题：往返法

    本研究提出一种迭代方法来高效地解决一类严格凸代价函数的最优运输问题，该方法包括二次和 p 次幂代价函数。我们针对两个定义在离散网格上的概率分布，使用 O (n) 的存储空间和 O (n log (n)) 的操作量计算最优映射，具有近似指数收敛速度。该方法能够在几分钟内解决空间网格大小达到 4096x4096 和 384x384x384 的最优运输问题。

    May, 2019

  • 通过加速梯度下降实现高效最优传输算法

    本研究提出了一种基于 Nesterov 的平滑技术的新算法，通过近似 Log-Sum-Exp 函数来平滑 Kantorovich 势的非平滑 c-transform，并将此平滑后的 Kantorovich 泛函应用于快速的 FISTA 算法以提高计算效率和精确度。实验结果表明，该方法相较于 Sinkhorn 算法在相同参数下具有更快的收敛速度和更高的准确性。

    Apr, 2021

  • 最优传输：带精确求解器的快速概率逼近

    本文提出了一个基于离散最优输运问题的简单子抽样方案，用于快速随机近似计算最优输运距离。该方案针对完全数据的随机子集操作，可使用任何精确算法作为黑盒后端，包括最先进的求解器和熵惩罚版本。我们给出了其非渐进偏差范围，以针对更高的精度或更短的计算时间进行简化。实验证明，该子抽样方案可以在计算时间大大降低的情况下，获得比精确方法更好的近似效果。

    Feb, 2018

  • 小批量 Wasserstein 学习：渐近和梯度特性

    本文对最优传输距离的使用进行了探索，指出在大规模数据集上计算这些距离的方法是通过平均几个较小的最优传输问题的结果。我们论证了这种方法等效于原问题的隐式正则化，并具有无偏估计，梯度和期望值周围的集中度约束等吸引人的属性。同时我们还开展了梯度流、GAN 或颜色转换等经验实验，以突出这种策略的实际价值。

    Oct, 2019