通过加速梯度下降实现高效最优传输算法
本研究分析了逼近两个离散分布之间的一般最优运输(OT)距离的两种算法,并证明了复杂度界限,其中一种基于 Sinkhorn 算法,另一种基于 Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) 算法。与先前的最优界限相比,我们的算法具有更好的复杂度界限,更好地依赖于 ε,同时可用于各种正则项。
Feb, 2018
本文研究了满足等式和不等式约束条件下的熵正则化的最优输运问题,并提出了一种基于 Sinkhorn 算法的对应解法。通过理论保证,我们首先得出在解决问题时通过熵正则化所带来的近似误差随着参数增加而指数级减小。此外,通过描述具有李雅普诺夫函数的优化过程,我们证明了 Sinkhorn 算法在对偶空间中具有亚线性一阶收敛速度。为了在弱熵正则化下实现快速、高阶收敛,我们通过动态正则化调度和二阶加速技术来改进 Sinkhorn 算法。总体而言,本文将熵最优输运的最近理论和数值进展与约束情况相结合,使从业者能够在复杂场景中得到近似的输运计划。
Mar, 2024
本文研究了两个非平衡度量之间的部分最优输运(Partial Optimal Transport,POT)问题及其在颜色转移或领域适应等各种人工智能任务中的应用。我们首先通过理论和实验证明了现有的 Sinkhorn 算法在 POT 问题上的不可行性,进而提出了一种新的 POT 算法来解决这一问题,并且提供了几种近似 POT 问题的一阶方法,其中包括了近似解在 ε 范围内的 Adaptive Primal-Dual Accelerated Gradient Descent(APDAGD)算法以及具有最佳计算复杂度的 Dual Extrapolation 算法。同时,我们还展示了 POT 相比标准 OT 的灵活性以及我们算法在两个非平衡边缘分布的实际应用中的实用性。
Dec, 2023
本文提供了计算复杂度分析 Sinkhorn 算法,用于解决两个若干可能具有不同质量组分的测量之间的熵正则化不平衡最优运输问题,其复杂度为近线性时间,该算法与最优运输问题的复杂度相比要更优。
Feb, 2020
本文提出两种有效的对数线性时间逼近方法来计算熵正则化最优输运问题,并提出了一种结合图神经网络和增强 Sinkhorn 的图输运网络,并实验证明它在节点数量方面具有对数线性的规模,并在图距离回归方面优于以前的模型 48%。
Jul, 2021
核密度估计方法在处理高维度的可行域问题方面比线性规划方法在统计效率上更加高效,但由于使用了大量迭代计算,使得该方法对于样本数量的扩展性较差。为了提高该方法在大样本情况下的可伸缩性,本文提出了一种基于核密度估计的非光滑定点模型,并通过专门的半光滑牛顿方法来高效地求解该模型,证明了该方法具有全局收敛速度 O (1/√k) 和在标准正则性条件下的局部二次收敛速度,并在合成数据集和真实数据集上显示了相对于使用短步内点法的显著加速。
Oct, 2023
我们设计了一种新的算法来计算最优运输成本,该算法结合了熵最优运输、镜像下降和共轭梯度文献,能够高效地在 GPU 上实现,表现出更快的迭代收敛速度,并能适应高熵边际分布的复杂优化问题,我们在 MNIST 数据集上进行了实验,结果显示该算法是实践者最佳运输工具包中有用的补充。
Jul, 2023
使用最优传输距离(OT)和尤其是熵正则化 OT 距离作为机器学习和数据科学中的一种评估度量越来越普遍。本研究主要针对在线 Sinkhorn 算法进行改进和优化,提出了改进的收敛性分析和压缩技术结合的在线 Sinkhorn 算法,通过实证实验和理论证明验证了方法的有效性和性能。
Oct, 2023