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

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Optimal Transport: Fast Probabilistic Approximation with Exact Solvers

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

The Garden Room, Ground Floor, new Library Building Heart and Lung Research Institute (0.R100&101&102) Old Combination Room, Trinity College, Cambridge

Other talks

CPH IRC and PHI CSAR lecture: In a post-Ozempic world, have we cured obesity? From lab to clinic: an introduction to translational research Title to be confirmed Tea and Coffee Break Shape modes of CP^1 vortices
 

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