A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance
A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance
复制标题
DOI：
--
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Minhui Huang;Shiqian Ma;L. Lai
中科院分区：
文献类型：
--
作者：
Minhui Huang;Shiqian Ma;L. Lai
沃瑟斯坦距离在机器学习和深度学习中变得越来越重要。尽管沃瑟斯坦距离很受欢迎，但由于维度的诅咒，它很难接近。最近提出的一种缓解维度灾难的方法是将采样数据从高维概率分布投影到低维子空间，然后计算投影数据之间的Wasserstein距离。然而，这种方法需要解决Stiefel流形上的极大极小问题，这在实践中是非常具有挑战性的。现有的唯一直接解决这一问题的工作是RGAS(Riemannian Gendent Ascent With Sinkhorn Iteration)算法，该算法需要在每次迭代中求解一个熵正则的最优传输问题，因此对于大规模问题来说代价可能很高。本文基于Stiefel流形上正则化的极大极小问题的一种新形式，提出了一种黎曼块坐标下降(RBCD)方法来解决这一问题。证明了RBCD获得$-驻点的算术运算复杂度为$O(-3})$.这显著提高了RGA的相应复杂性，即$O(\epsilon^{-12})$。此外，我们的RBCD具有很低的单次迭代复杂度，因此适用于大规模问题。在合成数据集和真实数据集上的数值结果表明，该方法比现有方法更有效，特别是在样本数据量很大的情况下。
The Wasserstein distance has become increasingly important in machine learning and deep learning. Despite its popularity, the Wasserstein distance is hard to approximate because of the curse of dimensionality. A recently proposed approach to alleviate the curse of dimensionality is to project the sampled data from the high dimensional probability distribution onto a lower-dimensional subspace, and then compute the Wasserstein distance between the projected data. However, this approach requires to solve a max-min problem over the Stiefel manifold, which is very challenging in practice. The only existing work that solves this problem directly is the RGAS (Riemannian Gradient Ascent with Sinkhorn Iteration) algorithm, which requires to solve an entropy-regularized optimal transport problem in each iteration, and thus can be costly for large-scale problems. In this paper, we propose a Riemannian block coordinate descent (RBCD) method to solve this problem, which is based on a novel reformulation of the regularized max-min problem over the Stiefel manifold. We show that the complexity of arithmetic operations for RBCD to obtain an $\epsilon$-stationary point is $O(\epsilon^{-3})$. This significantly improves the corresponding complexity of RGAS, which is $O(\epsilon^{-12})$. Moreover, our RBCD has very low per-iteration complexity, and hence is suitable for large-scale problems. Numerical results on both synthetic and real datasets demonstrate that our method is more efficient than existing methods, especially when the number of sampled data is very large.