Optimal transport (OT) is a kind of problem that tries to find the best way to transport resources in a given shape to another given shape. Despite the deceptively simple definition, the process by which OT is solved for in computational problems is usually too costly a process for many needs.

A new algorithm, dubbed SPOT, is able to solve OT problems in a scalable, computationally inexpensive manner. SPOT is also the first algorithm that is able to effectively solve the OT problem in a continuous case, which was once labeled as prohibitive.

“In many cases, OT problems are considered computationally prohibitive,” said School of Computational Science and Engineering (CSE) Ph.D. Student Yujia Xie, the primary investigator of the study.

“One such example is in high-dimensional continuous cases. For continuous cases, people used to discretize the space first, then treat the problem as a discrete optimization problem. However, the computation is very expensive. This makes the high-dimensional problem prohibitive. SPOT is able to solve such problems efficiently, which is a greatly liberating move towards more effective transport for computational needs.”

The optimal transport problem has a long history that dates back to 1781. It has wide applications, including applied mathematics, economy and geography. One of its important uses is to compare how close two probability distributions are. 

“Our algorithm not only gives an elegant solution to optimal transport problems seen in computational applications, but also provides an example of how to apply recently developed implicit generative tools to challenges with a long history. Hopefully, people can become inspired by the idea in solving other challenges.”

Xie will present the findings of this paper on Thursday June 13, 2019 at the Thirty-sixth International Conference on Machine Learning.