最优传输的退火Sinkhorn：收敛性、正则化路径和去偏差
内容提要
本文提出了一系列新算法解决最优输运问题，包括APDAMD、Semi-Relaxed Sinkhorn和Sinkhorn-Newton-Sparse，展示了它们在效率和收敛性上的优势。同时，研究探讨了不平衡输运和部分最优输运问题的应用，提供了理论保证和实用算法，推动了相关领域的发展。
延伸解读
算法演进：从加速到超指数收敛
文章梳理了最优传输求解算法的演进脉络：APDAMD针对原子最优传输，结合交替最小化与Nesterov加速，无需凸性先验；Semi-Relaxed Sinkhorn首次为半松弛问题提供理论收敛分析；Sinkhorn-Newton-Sparse通过早停止和牛顿子程序实现超指数收敛，实际速度比经典Sinkhorn快数个数量级。这些进展共同推动了求解效率的边界。
理论保证：收敛性与近似误差
多个工作提供了严格的理论保证：不平衡输运的熵正则化算法被证明具有线性收敛性；Semi-Relaxed Sinkhorn给出了功能价值差、边际约束差和OT距离的收敛上限；对于带约束的熵正则化问题，近似误差随参数增加指数级减小，且Sinkhorn在对偶空间具有亚线性一阶收敛速度。这些结果为算法可靠性奠定了基础。
应用拓展：从颜色转移到领域适应
文章展示了算法在人工智能任务中的实际应用，包括颜色转移和领域适应。部分最优传输（POT）相比标准OT更灵活，能处理非平衡边缘分布；Screenkhorn通过筛选双重组件高效近似Sinkhorn距离，在降维和领域适应中表现高效。这些应用表明最优传输正成为处理分布不匹配问题的实用工具。
未来方向：广义化与约束处理
近期研究将经典最优局部传输推广到广义形式，通过修改质量破坏/创建项引入新问题，并讨论其对偶形式和Sinkhorn求解器。同时，带等式和不等式约束的熵正则化最优传输得到关注，动态正则化调度和二阶加速技术被用于在弱正则化下实现快速高阶收敛。这些方向扩展了最优传输的建模能力。
Q&A
APDAMD算法的主要优势是什么？
APDAMD算法在解决原子最优输运问题时具有较高的效率。
Semi-Relaxed Sinkhorn算法的应用是什么？
Semi-Relaxed Sinkhorn算法用于求解半松弛最优输运问题，并提供了理论收敛分析。
Sinkhorn-Newton-Sparse算法的收敛速度如何？
Sinkhorn-Newton-Sparse算法提供超指数收敛，收敛速度快于Sinkhorn算法。
如何实现不平衡输运的熵正则化？
通过基于标准Sinkhorn更新和紧缩函数的交替迭代算法来实现不平衡输运的熵正则化。
部分最优输运问题在人工智能中的应用有哪些？
部分最优输运问题在颜色转移和领域适应等人工智能任务中有广泛应用。
如何提高Sinkhorn算法的收敛速度和准确性？
通过近似Log-Sum-Exp函数和应用快速的FISTA算法来提高Sinkhorn算法的收敛速度和准确性。
