Mar, 2024

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

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

    本文提出了一种针对离散最优输运问题的平滑凸正则化统一框架，并基于 Bregman 差异将正则化最优输运等效于矩阵相似问题，其中的算法包括基于 Sinkhorn-Knopp 以及 Dykstra 的交替投影算法，以及基于牛顿-拉夫逊法的扩展算法。此外，还将该框架应用到了机器学习和信息几何等领域，并通过实验进行了验证。

    Oct, 2016

  • 平滑且稀疏最优输运

    本文探讨在最优输运问题的原始和对偶形式中引入强凸项的正则化方法，以产生稀疏和群稀疏输送计划，并在颜色转移任务上展示了该框架的应用。

    Oct, 2017

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

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

    Mar, 2018

  • 使用Wasserstein距离的Sinkhorn逼近的微分特性

    应用最优输运及熵正则化计算Wasserstein距离中的Sinkhorn近似算法的梯度，可以提高学习和优化问题的效率，同时通过高阶平滑性，也可以提供统计保证。

    May, 2018

  • 熵正则算法在最优输运中的效率

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

    Jun, 2019

  • 交替最小化和 Nesterov 动量方法的组合

    本文提出一种结合Alternating minimization（AM）和Nesterov's acceleration的自适应加速交替最小化算法，可用于解决具有凸性和非凸性的优化问题，同时不需要任何有关问题的凸性或函数参数等知识。通过证明该算法的收敛速度，得出该方法是自适应且优化的。此外还为具有线性约束的强凸问题开发了其原始-对偶修改。

    Jun, 2019

  • 正则化最优输运的理论是基于地面成本对抗的

    本研究提出了一个新的正则化解释角度，即将正则化视为一种鲁棒性机制，展示了任何凸正则化的OT都可以被解释为接受对手--地面成本的方式。这同时可以在地面空间上提供鲁棒的不相似性度量方法，并提出了相应的算法和实验性说明了这种方法的优越性。

    Feb, 2020

  • 无偏Sinkhorn重心

    本文研究优化输运中的熵正则化对Wasserstein度量和重心的影响，提出了一种去偏差的Wasserstein重心方法，能够在保持快速的Sinkhorn迭代的同时避免了熵平滑。理论上证明了单峰高斯函数的熵输运重心是高斯函数，并量化了其方差偏差。同时通过实验验证了该方法的优越性。

    Jun, 2020

  • Sinkhorn Flow: Sinkhorn算法的连续时间框架解读与推广

    机器学习中的熵正则最优传输问题可以通过Sinkhorn算法进行求解，而该研究介绍了Sinkhorn算法的连续时间模拟以及其在噪声和偏差容忍性方面的改进，同时与机器学习和数学领域中其他动态方法提供了统一的视角。

    Nov, 2023

  • 稀疏牛顿迭代加速Sinkhorn算法

    通过引入早停止和牛顿类型子程序，Sinkhorn-Newton-Sparse（SNS）算法提供了超指数收敛，并且在实际情况下收敛速度比Sinkhorn算法快几个数量级，包括离散密度的经验分布之间的最优输运和计算Wasserstein W1，W2距离。

    Jan, 2024