University of Cambridge > Talks.cam > Statistics > Optimal Transport: Fast Probabilistic Approximation with Exact Solvers

Optimal Transport: Fast Probabilistic Approximation with Exact Solvers

Add to your list(s) Download to your calendar using vCal

  • UserYoav Zemel, University of Cambridge
  • ClockFriday 24 January 2020, 14:00-15:00
  • HouseMR12.

If you have a question about this talk, please contact Dr Sergio Bacallado.

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. It is based on averaging the exact distances between empirical measures generated from independent samples from the original measures and can easily be tuned towards higher accuracy or shorter computation times. To this end, we give non-asymptotic deviation bounds for its accuracy in the case of discrete optimal transport problems. In particular, 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 that demonstrate that a very good approximation in typical applications can be obtained in a computation time that is several orders of magnitude smaller than what is required for exact computation of the full problem.

This talk is part of the Statistics series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity