PREVIOUS SEMINAR - 23rd October 2020

Speaker: Yoav Zemel (University of Cambridge)

Title: Probabilistic approximations to optimal transport

Abstract: Optimal transport is now a popular tool in statistics, machine learning, and data science. A major challenge in applying optimal transport to large-scale problems is its excessive computational cost. We propose a simple subsampling scheme for fast randomized approximate computation of optimal transport distances on finite spaces. This scheme operates on a random subset of the full data and can use any exact algorithm as a black-box back-end, including state-of-the-art solvers and entropically penalized versions. We give non-asymptotic deviation bounds for its accuracy in the case of discrete optimal transport problems, and show that in many important instances, including images (2D-histograms), the approximation error is independent of the size of the full problem. We present numerical experiments demonstrating very good approximation can be obtained while decreasing the computation time by several orders of magnitude.

We will also discuss further, recently obtained results on the limiting distribution of the optimal transport plan.