Sinkhorn 算法重要性稀疏化
本文提供了计算复杂度分析 Sinkhorn 算法,用于解决两个若干可能具有不同质量组分的测量之间的熵正则化不平衡最优运输问题,其复杂度为近线性时间,该算法与最优运输问题的复杂度相比要更优。
Feb, 2020
使用最优传输距离(OT)和尤其是熵正则化 OT 距离作为机器学习和数据科学中的一种评估度量越来越普遍。本研究主要针对在线 Sinkhorn 算法进行改进和优化,提出了改进的收敛性分析和压缩技术结合的在线 Sinkhorn 算法,通过实证实验和理论证明验证了方法的有效性和性能。
Oct, 2023
本文研究了满足等式和不等式约束条件下的熵正则化的最优输运问题,并提出了一种基于 Sinkhorn 算法的对应解法。通过理论保证,我们首先得出在解决问题时通过熵正则化所带来的近似误差随着参数增加而指数级减小。此外,通过描述具有李雅普诺夫函数的优化过程,我们证明了 Sinkhorn 算法在对偶空间中具有亚线性一阶收敛速度。为了在弱熵正则化下实现快速、高阶收敛,我们通过动态正则化调度和二阶加速技术来改进 Sinkhorn 算法。总体而言,本文将熵最优输运的最近理论和数值进展与约束情况相结合,使从业者能够在复杂场景中得到近似的输运计划。
Mar, 2024
通过引入早停止和牛顿类型子程序,Sinkhorn-Newton-Sparse(SNS)算法提供了超指数收敛,并且在实际情况下收敛速度比 Sinkhorn 算法快几个数量级,包括离散密度的经验分布之间的最优输运和计算 Wasserstein W1,W2 距离。
Jan, 2024
本文研究优化输运中的熵正则化对 Wasserstein 度量和重心的影响,提出了一种去偏差的 Wasserstein 重心方法,能够在保持快速的 Sinkhorn 迭代的同时避免了熵平滑。理论上证明了单峰高斯函数的熵输运重心是高斯函数,并量化了其方差偏差。同时通过实验验证了该方法的优越性。
Jun, 2020
本文提出使用低秩近似的 ground costs 方法来提高 Sinkhorn divergences 计算效率,并将该方法应用于训练 OT-GAN 模型。
Jun, 2020
本文介绍了一种使用最优输送损失的可行计算方法,通过熵平滑和自动微分来减少计算负担、提高稳定性和平滑性,获得鲁棒和可微分的最优输送损失的逼近,从而训练大规模生成模型并补充标准深度网络生成模型的计算机架构。
Jun, 2017
本研究提出了一种基于 Nesterov 的平滑技术的新算法,通过近似 Log-Sum-Exp 函数来平滑 Kantorovich 势的非平滑 c-transform,并将此平滑后的 Kantorovich 泛函应用于快速的 FISTA 算法以提高计算效率和精确度。实验结果表明,该方法相较于 Sinkhorn 算法在相同参数下具有更快的收敛速度和更高的准确性。
Apr, 2021