BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Statistics
SUMMARY:Optimal Transport: Fast Probabilistic Approximatio
n with Exact Solvers - Yoav Zemel\, University of
Cambridge
DTSTART;TZID=Europe/London:20200124T140000
DTEND;TZID=Europe/London:20200124T150000
UID:TALK137599AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/137599
DESCRIPTION:We propose a simple subsampling scheme for fast ra
ndomized approximate computation of optimal transp
ort distances on finite spaces. This scheme operat
es on a random subset of the full data and can use
any exact algorithm as a black-box back-end\, inc
luding state-of-the-art solvers and entropically p
enalized versions. It is based on averaging the ex
act distances between empirical measures generated
from independent samples from the original measur
es and can easily be tuned towards higher accuracy
or shorter computation times. To this end\, we gi
ve non-asymptotic deviation bounds for its accurac
y in the case of discrete optimal transport proble
ms. In particular\, we show that in many important
instances\, including images (2D-histograms)\, th
e approximation error is independent of the size o
f the full problem. We present numerical experimen
ts that demonstrate that a very good approximation
in typical applications can be obtained in a comp
utation time that is several orders of magnitude s
maller than what is required for exact computation
of the full problem.
LOCATION:MR12
CONTACT:Dr Sergio Bacallado
END:VEVENT
END:VCALENDAR