Computational optimal transport

Optimal transport (OT) problem is a mathematical problem of more than 200 years’ history. It is closely related to the basic concept – Wasserstein distance that compares probability distributions. This concept is widely used in image processing, decision science, and machine learning. However, how to efficiently solve the optimal transport problem is still an open question. To approximate the solution, people often formulate and solve a large-scale linear programming (LP) problem with special structure. We aim to design reliable and fast algorithms to solve this LP. These algorithms are expected to have competitive practical performance and/or theoretical guarantees compared to existing state-of-art algorithms for optimal transport, most of which are Sinkhorn based.

In our recent work, we consider random block coordinate descent (RBCD) methods to directly solve the related LP. In each iteration, we restrict the potential large-scale optimization problem to small LP subproblems constructed via randomly chosen working sets. Using an expected Gauss-Southwell-q rule to select these working sets, we equip a vanilla version with almost sure convergence and linear convergence rate in expectation to solve a general LP problem. By further exploring the special structure of constraints in the OT problems and leveraging the theory of linear systems, we proposed several approaches to refine the random working set selection and accelerate the vanilla method. Preliminary numerical experiments verify the acceleration effects, solution sparsity and demonstrate several merits of an accelerated random block coordinate descent over the Sinkhorn’s algorithm when seeking highly accurate solutions. (https://arxiv.org/abs/2212.07046)

Algorithm study for constrained optimization

Constrained optimization becomes increasingly useful in modelling applications in data science. For example, people add manifold constraints, nonnegative constraints or sparsity constraints for training tasks in machine learning and image processing; the minimax problem – math model of generative adversarial network (GAN), is also closely related to constrained optimization. We are interested in studying efficient algorithms to solve this problem class, including methods of multiplier, operator splitting methods, proximal point methods, primal dual methods and projection methods, etc. Due to the nonconvex nature of many modern optimization problems, first-order stationary solution is no longer satisfying, and we study how these classical methods can find solutions of higher-order stationarity efficiently and provide good complexity guarantees. In the context of big data, optimization problem is often complicated by expected-valued functions and finite sums, so stochastic methods assumes more relevance. Therefore, we are also engaged in investigating the convergence properties of these classical optimization methods in the stochastic setting.