MMAug, 2020

带结构的多边际最优传输问题的多项式时间算法

PDF
TL;DR本论文提出了一种通用的理论框架和算法，通过利用简单的变形来解决多边际最优输运问题（MOT）在多项式时间内，尤其是解决了当前最流行的 Sinkhorn 算法对于 MOT 求解在多项式时间内所需要的额外结构，提供了新的精确且稀疏的算法，同时对于三种 MOT 成本结构提供了可充分利用标准算法技术的多项式时间算法。
multimarginal optimal transportstructurealgorithmpoly(n,k) timedual feasibility oracle
发现论文，激发创造
  • 关于多边际最优输运近似复杂度的研究

    本文研究了多项式最优运输（MOT）距离的近似复杂性，提出了两个新的确定性算法：多重边缘 Sinkhorn 算法和加速多重边缘 Sinkhorn 算法。通过实验，证明了这两种算法在计算效率和准确性上的优越性。

    Sep, 2019

  • 多边际最优输运问题的困难度结果

    该研究是对 Multimarginal Optimal Transport 问题进行的一项研究，重点是解决该问题的复杂性，并使用工具包证明其 NP 难度以及近似不可能性，此外我们通过论证证明各种拒斥成本使 MOT 问题成为 NP 难的实际困难。

    Dec, 2020

  • 多边际最优输运：理论与应用

    本篇综述介绍了近五年来备受关注的多重边际最优输运问题，包括其在 Monge-Kantorovich 问题上的推广、解的独特性、结构和代价函数。我们回答了这些问题，揭示了它与传统的两个边际模型的密切关系，以及与代价函数之间的微妙依赖关系。此外，本文还介绍了多重边际问题的两个应用。

    May, 2014

  • 结构稀疏最优传输的子模组框架

    探索在不平衡最优输运 (UOT) 设置中学习稀疏输运规划，提出基于最大均值差异 UOT 的稀疏约束优化问题，开发了高效的基于梯度的离散贪婪算法，并在多个应用中验证了该方法的有效性。

    Jun, 2024

  • 关于部分最优输运：修正 Sinkhorn 和高效梯度方法的不可行性

    本文研究了两个非平衡度量之间的部分最优输运（Partial Optimal Transport，POT）问题及其在颜色转移或领域适应等各种人工智能任务中的应用。我们首先通过理论和实验证明了现有的 Sinkhorn 算法在 POT 问题上的不可行性，进而提出了一种新的 POT 算法来解决这一问题，并且提供了几种近似 POT 问题的一阶方法，其中包括了近似解在 ε 范围内的 Adaptive Primal-Dual Accelerated Gradient Descent（APDAGD）算法以及具有最佳计算复杂度的 Dual Extrapolation 算法。同时，我们还展示了 POT 相比标准 OT 的灵活性以及我们算法在两个非平衡边缘分布的实际应用中的实用性。

    Dec, 2023

  • 元最优输运

    该论文研究了利用折旧优化技术来预测最优输运映射的应用，称之为 “元优化传输”（Meta OT)。它提高了标准方法的计算效率，并改进了收敛速率。

    Jun, 2022

  • 关于不平衡最优输运的 Sinkhorn 算法分析

    本文提供了计算复杂度分析 Sinkhorn 算法，用于解决两个若干可能具有不同质量组分的测量之间的熵正则化不平衡最优运输问题，其复杂度为近线性时间，该算法与最优运输问题的复杂度相比要更优。

    Feb, 2020

  • 多边际最优输运与概率图模型

    本文从概率图形模型角度研究了多边际最优输运问题。当最优输运的成本允许图形结构时，我们指出了二者之间的一个优雅的联系。特别地，通过熵正则化的多边际最优输运等价于概率图形模型的贝叶斯边际推断问题，其中附加了一些边际分布要求的条件。这种关系一方面扩展了最优输运和概率图形模型的理论，另一方面通过利用贝叶斯推断中成熟的算法，实现了多边际最优输运的快速算法。还提供了几个数值例子以突出结果。

    Jun, 2020

  • 计算多类别分类中对抗训练下界的最优输运方法

    利用多边际最优传输 （MOT） 将对抗性风险问题简化为线性规划和熵正则化的数值算法，以提高深度学习模型的鲁棒性。

    Jan, 2024

  • 低秩 Sinkhorn 分解

    本研究基于低秩约束探索了一种求解任意代价的最优输运问题的泛用性算法，并通过基准实验验证其效率。

    Mar, 2021