论文标题
Riemannian指数增强的拉格朗日方法，用于计算投影强大的瓦斯坦距离
A Riemannian exponential augmented Lagrangian method for computing the projection robust Wasserstein distance
论文作者
论文摘要
将距离度量投射到低维空间上是一种有效的方法，可以使用最佳运输来减轻经典的Wasserstein距离的尺寸诅咒。获得的最大距离称为投影强大的瓦斯坦（PRW）距离。在本文中，我们等同地将PRW距离的计算重新制定为Stiefel歧管和欧几里得空间的笛卡尔产品的优化问题，并具有其他非线性不平等约束。我们提出了一种Riemannian指数增强Lagrangian方法（领域），并具有全球收敛保证，以解决此问题。与现有方法相比，领域可能会避免罚款参数太小。此外，我们提出了一个不精确的riemannian梯度下降方法的框架，以有效地解决领域的子问题。特别是，通过使用子问题的特殊结构，我们给出了一种实用算法，称为不精确的riemannian barzilai-borwein方法，其中具有sndhorn迭代（IRBBS）。 IRBB的显着特征在于，它执行了灵活数量的sndhorn迭代，以计算问题的投影矩阵，并采用Barzilai-Borwein基于不精确的梯度信息，以提高性能。我们表明，IRBB可以返回$ \ Mathcal {O}（ε^{ - 3}）$ iterations $ \ Mathcal {O}中原始PRW距离问题的$ε$ - 定位点。关于合成和真实数据集的广泛数值结果表明，我们提出的领域以及IRBB的表现优于计算PRW距离的最新求解器。
Projecting the distance measures onto a low-dimensional space is an efficient way of mitigating the curse of dimensionality in the classical Wasserstein distance using optimal transport. The obtained maximized distance is referred to as projection robust Wasserstein (PRW) distance. In this paper, we equivalently reformulate the computation of the PRW distance as an optimization problem over the Cartesian product of the Stiefel manifold and the Euclidean space with additional nonlinear inequality constraints. We propose a Riemannian exponential augmented Lagrangian method (ReALM) with a global convergence guarantee to solve this problem. Compared with the existing approaches, ReALM can potentially avoid too small penalty parameters. Moreover, we propose a framework of inexact Riemannian gradient descent methods to solve the subproblems in ReALM efficiently. In particular, by using the special structure of the subproblem, we give a practical algorithm named as the inexact Riemannian Barzilai-Borwein method with Sinkhorn iteration (iRBBS). The remarkable features of iRBBS lie in that it performs a flexible number of Sinkhorn iterations to compute an inexact gradient with respect to the projection matrix of the problem and adopts the Barzilai-Borwein stepsize based on the inexact gradient information to improve the performance. We show that iRBBS can return an $ε$-stationary point of the original PRW distance problem within $\mathcal{O}(ε^{-3})$ iterations. Extensive numerical results on synthetic and real datasets demonstrate that our proposed ReALM as well as iRBBS outperform the state-of-the-art solvers for computing the PRW distance.
