New Algorithms for Optimal Transport Problems

Dr. Shiqian Ma
University of Houston - Melcher Hall 180

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 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.


Shiqian Ma is currently an associate professor in the Department of Computational Applied Mathematics and Operations Research at Rice University, and in the Department of Mathematics at University of California, Davis (on leave). He received his PhD in Industrial Engineering and Operations Research from Columbia University in 2011. Before joining Rice University, Shiqian has held positions at University of Minnesota, Chinese University of Hong Kong, and UC Davis. His current research interests include theory and algorithms for large-scale optimization, and their various applications in machine learning, signal processing and statistics. Shiqian has served as the area chairs for machine learning conferences such as ICML and NeurIPS and currently serves on the editorial board of Journal of Scientific Computing.