Recent years have witnessed an ever-increasing role for ideas from optimal transport (OT) in statistics and machine learning, while a significant barrier to the direct application of OT lies in some inherent statistical limitations. It is well known that the sample complexity of approximating Wasserstein distances between densities using only samples can grow exponentially in dimension. In order to offer an alternative, functional estimation procedure to address OT problems from samples, several variants of the OT distance are proposed, including projection OT distance and kernel OT distance. The resulting estimators are shown to be more statistically efficient than plug-in (linear programming-based) OT estimators when comparing probability measures in high-dimensions. Unfortunately, that statistical benefit comes at a very steep computational price: because their computation relies on solving much more complicated optimization problems, these estimators quickly become intractable as the sample size increases. In this talk, I will present the results on computing projection OT distance and kernel OT distance. More specifically, by exploiting special structures, we show that these two OT distances can be efficiently solved via Riemannian gradient-based methods and a specialized semismooth Newton method, respectively. Finally, I summarize the statistical-computational trade-off in the context of OT and discuss some future research directions.

Tianyi Lin is currently an assistant professor in the Department of Industrial Engineering and Operations Research (IEOR) at Columbia University. His research interests lie in optimization and machine learning, game theory, social and economic network, and optimal transport. He obtained his Ph.D. in Electrical Engineering and Computer Science at UC Berkeley, where he was advised by Professor Michael Jordan and was associated with the Berkeley Artificial Intelligence Research (BAIR) group. From 2023 to 2024, he was a postdoctoral researcher at the Laboratory for Information & Decision Systems (LIDS) at Massachusetts Institute of Technology, working with Professor Asuman Ozdaglar. Prior to that, he received a B.S. in Mathematics from Nanjing University, a M.S. in Pure Mathematics and Statistics from University of Cambridge and a M.S. in Operations Research from UC Berkeley.