Optimal Transport: Fast Probabilistic Approximation with Exact Solvers

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

• Yoav Zemel, University of Cambridge
• Friday 24 January 2020, 14:00-15:00
• MR12.

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.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Guy Emerson's list
• Hanchen DaDaDash
• Interested Talks
• MR12
• Machine Learning
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Statistics
• Statistics Group
• bld31
• custom
• rp587

Note that ex-directory lists are not shown.