论文标题
计算最佳传输的随机方法，而无需正则化及其收敛分析
Randomized methods for computing optimal transport without regularization and their convergence analysis
论文作者
论文摘要
可以通过离散化将最佳传输（OT）问题简化为线性编程（LP）问题。在本文中，我们引入了随机块坐标下降（RBCD）方法，以直接解决此LP问题。我们的方法涉及将潜在的大规模优化问题限制为通过随机选择的工作组构建的小型LP子问题。通过使用随机的高斯 - 南威尔 - $ Q $规则来选择这些工作集，我们为（$ {\ bf {\ rm rm rbcd} _0} $）配备了Vanilla版本，几乎可以肯定收敛和线性收敛速率来求解一般标准LP问题。为了进一步提高（$ {\ bf {\ rm rbcd} _0} $）方法的效率，我们探讨了OT问题中约束的特殊结构，并利用线性系统的理论提出了几种改进随机工作集选择和加速香草方法的方法。还讨论了RBCD方法的不确定版本。我们的初步数值实验表明，加速的随机块坐标下降（$ {\ bf {\ rm arbcd}} $）方法可以与其他求解器进行良好的比较，包括以相对较高的准确性来寻求解决方案，并提供保存记忆的优势。
The optimal transport (OT) problem can be reduced to a linear programming (LP) problem through discretization. In this paper, we introduced the random block coordinate descent (RBCD) methods to directly solve this LP problem. Our approach involves restricting the potentially large-scale optimization problem to small LP subproblems constructed via randomly chosen working sets. By using a random Gauss-Southwell-$q$ rule to select these working sets, we equip the vanilla version of (${\bf{\rm RBCD}_0}$) with almost sure convergence and a linear convergence rate to solve general standard LP problems. To further improve the efficiency of the (${\bf{\rm RBCD}_0}$) method, we explore the special structure of constraints in the OT problems and leverage the theory of linear systems to propose several approaches for refining the random working set selection and accelerating the vanilla method. Inexact versions of the RBCD methods are also discussed. Our preliminary numerical experiments demonstrate that the accelerated random block coordinate descent (${\bf {\rm ARBCD}}$) method compares well with other solvers including Sinkhorn's algorithm when seeking solutions with relatively high accuracy, and offers the advantage of saving memory.
