BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Optimal Transport: Fast Probabilistic Approximation with Exact Sol
 vers - Yoav Zemel\, University of Cambridge
DTSTART:20200124T140000Z
DTEND:20200124T150000Z
UID:TALK137599@talks.cam.ac.uk
CONTACT:Dr Sergio Bacallado
DESCRIPTION:We propose a simple subsampling scheme for fast randomized app
 roximate 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 an
 d entropically penalized versions. It is based on averaging the exact dist
 ances between empirical measures generated from independent samples from t
 he original measures and can easily be tuned towards higher accuracy or sh
 orter computation times. To this end\, we give non-asymptotic deviation bo
 unds for its accuracy in the case of discrete optimal transport problems. 
 In particular\, we show that in many important instances\, including image
 s (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 comp
 utation time that is several orders of magnitude smaller than what is requ
 ired for exact computation of the full problem.
LOCATION:MR12
END:VEVENT
END:VCALENDAR