New Algorithms for Optimal Transport Problems

In this talk, we consider two problems related to optimal transport. The first problem is called the projection robust optimal transport, which can mitigate the curse of dimensionality of optimal transport. The projection robust optimal transport can be formulated as a max-min problem over the Stiefel manifold, which is very challenging in practice. We propose a Riemannian block coordinate descent (RBCD) method to solve this problem. We analyze the complexity of arithmetic operations for RBCD to obtain an Ɛ-stationary point, and show that it significantly improves the corresponding complexity of existing methods. The second problem is called equitable optimal transport (EOT), which finds many applications such as fair division problems and optimal transport with multiple agents etc. In a recent work, Scetbon et.al proposed a projected alternating maximization algorithm (PAM) to solve the dual of the entropy regularized EOT. We provide the first convergence analysis of PAM. A novel rounding procedure is proposed to help construct the primal solution for the original EOT problem. We also propose a variant of PAM by incorporating the extrapolation technique that can numerically improve the performance of PAM. Our results may shed light on block coordinate (gradient) descent methods for general optimization problems.