平滑且稀疏最优输运
本文研究了满足等式和不等式约束条件下的熵正则化的最优输运问题,并提出了一种基于 Sinkhorn 算法的对应解法。通过理论保证,我们首先得出在解决问题时通过熵正则化所带来的近似误差随着参数增加而指数级减小。此外,通过描述具有李雅普诺夫函数的优化过程,我们证明了 Sinkhorn 算法在对偶空间中具有亚线性一阶收敛速度。为了在弱熵正则化下实现快速、高阶收敛,我们通过动态正则化调度和二阶加速技术来改进 Sinkhorn 算法。总体而言,本文将熵最优输运的最近理论和数值进展与约束情况相结合,使从业者能够在复杂场景中得到近似的输运计划。
Mar, 2024
本研究提出通过解决 Sinkhorn 算法中的不动点方程从而得到熵正则化两个高斯测度之间的最优输运问题的闭合形式解,甚至适用于协方差矩阵退化的高斯分布,同时阐明了非平衡最优输运中的质量输运 / 破坏权衡,其最优输运方案为高斯分布。
Jun, 2020
优化输运的原始表述引入了严格凸项以减少数值复杂度和增加输运计划的密度。然而,许多公式在输运计划上施加了全局约束,例如依赖于熵正则化。我们引入自适应正则化优化输运(OTARI),它对每个点的质量流入和 / 或流出施加约束,从而减少了质量均衡问题。我们展示了该方法在领域适应中的益处。
Oct, 2023
本研究提出了一个新的正则化解释角度,即将正则化视为一种鲁棒性机制,展示了任何凸正则化的 OT 都可以被解释为接受对手 -- 地面成本的方式。这同时可以在地面空间上提供鲁棒的不相似性度量方法,并提出了相应的算法和实验性说明了这种方法的优越性。
Feb, 2020
该论文提出了一种基于 group-sparse 正则化方法的快速离散最优传输算法,该算法可以在保证准确率的前提下提高计算速度,并在无监督域适应等领域有广阔的应用前景。
Mar, 2023
本文证明了熵正则化最优输运问题的 Gamma 收敛性,并证明了隐式步骤按熵正则化距离时收敛于原始梯度流,证明了压缩后的最优输运计划收敛于最优输运计划,这表明了压缩后的熵正则化最优输运计划在熵消失时收敛于最优输运计划。
Dec, 2015
本文提出两种有效的对数线性时间逼近方法来计算熵正则化最优输运问题,并提出了一种结合图神经网络和增强 Sinkhorn 的图输运网络,并实验证明它在节点数量方面具有对数线性的规模,并在图距离回归方面优于以前的模型 48%。
Jul, 2021
本文主要讨论了在源测度和目标测度均为次高斯测度的情况下,估计具有平方欧氏距离成本的熵正则化最优传输(EOT)映射的问题,并指出了在目标测度具有紧支集或强对数凹性时,即使采用了最近提出的样本内估计器,期望均方 $L^2$ 误差仅以至少 $O (n^{-1/3})$ 的速率衰减,而对于一般次高斯情况,期望 $L^1$ 误差以至少 $O (n^{-1/6})$ 的速率衰减,并且这些结果在正则化参数上具有多项式依赖性。由于这些结果消除了对紧支集的要求,因此尽管与源测度和目标测度均为紧支集(平方 $L^2$ 误差以速率 $O (n^{-1})$ 收敛)或源测度为次高斯而目标测度为紧支集(平方 $L^2$ 误差以速率 $O (n^{-1/2})$ 收敛)的已知结果相比还不够优化,但它们具有重要意义。证明技巧利用了偏差 - 方差分解,其中方差通过标准的集中度结果进行控制,而偏差则通过 T1 - 传输不等式以及在次高斯假设下估计 EOT 成本的样本复杂性结果来处理。实验结果显示了对方差项控制的松弛性,并最后提出了几个开放性问题。
Nov, 2023