ICMLJan, 2019

高效最优输运：贪婪算法和加速镜像下降算法分析

PDF
TL;DR我们提供两种算法的理论分析，这两种算法可以解决两个离散概率测度之间的规则化最优输运问题，我们证明了一种名为绿角（Greenkhorn）算法的贪心版本可以改进到 O˜（n²ε ^-2），这种算法可以在实践中击败 Sinkhorn 算法，基于这个理论我们提出了新的算法。
regularized optimal transportsinkhorn algorithmgreenkhorn algorithmprimal-dual formulationadaptive primal-dual accelerated mirror descent
发现论文，激发创造
  • 熵正则算法在最优输运中的效率

    我们提出了一种新的算法 APDAMD 来解决原子最优输运问题，并证明了算法的复杂度界限与加速变种的 Sinkhorn 算法和 Greenkhorn 算法，在实践中均具有较高的效率。

    Jun, 2019

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

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

    Feb, 2018

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

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

    Dec, 2023

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

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

    Apr, 2021

  • 熵正则化最优输运问题的贪婪随机算法

    本论文研究基于熵罚函数的最优传输问题的随机算法，这些算法速度较快、实用，并且在数值实验中验证了它们相对于最优传输方法的优势。

    Mar, 2018

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

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

    Feb, 2020

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

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

    May, 2017

  • 使用镜像下降与共轭梯度的高效准确最优输运

    我们设计了一种新的算法来计算最优运输成本，该算法结合了熵最优运输、镜像下降和共轭梯度文献，能够高效地在 GPU 上实现，表现出更快的迭代收敛速度，并能适应高熵边际分布的复杂优化问题，我们在 MNIST 数据集上进行了实验，结果显示该算法是实践者最佳运输工具包中有用的补充。

    Jul, 2023

  • 在线压缩 Sinkhorn

    使用最优传输距离（OT）和尤其是熵正则化 OT 距离作为机器学习和数据科学中的一种评估度量越来越普遍。本研究主要针对在线 Sinkhorn 算法进行改进和优化，提出了改进的收敛性分析和压缩技术结合的在线 Sinkhorn 算法，通过实证实验和理论证明验证了方法的有效性和性能。

    Oct, 2023

  • 一种用于约束优化传输问题的 Sinkhorn 类型算法

    本文研究了满足等式和不等式约束条件下的熵正则化的最优输运问题，并提出了一种基于 Sinkhorn 算法的对应解法。通过理论保证，我们首先得出在解决问题时通过熵正则化所带来的近似误差随着参数增加而指数级减小。此外，通过描述具有李雅普诺夫函数的优化过程，我们证明了 Sinkhorn 算法在对偶空间中具有亚线性一阶收敛速度。为了在弱熵正则化下实现快速、高阶收敛，我们通过动态正则化调度和二阶加速技术来改进 Sinkhorn 算法。总体而言，本文将熵最优输运的最近理论和数值进展与约束情况相结合，使从业者能够在复杂场景中得到近似的输运计划。

    Mar, 2024