Title: Stochastic approximations to optimal transport
Authors: Yoav Zemel - University of Cambridge (United Kingdom) [presenting]
Axel Munk - Georg-August-University Goettingen (Germany)
Marcel Klatt - Georg-August-University Goettingen (Germany)
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 high computational cost. We propose a simple resampling 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. We 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 the excellent approximation that 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.