English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Optimal transport: Fast probabilistic approximation with exact solvers.

MPS-Authors
/persons/resource/persons32719

Munk,  A.
Research Group of Statistical Inverse-Problems in Biophysics, MPI for biophysical chemistry, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

3149995.pdf
(Preprint), 694KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Sommerfeld, M., Schrieber, J., Zemel, Y., & Munk, A. (2019). Optimal transport: Fast probabilistic approximation with exact solvers. The Journal of Machine Learning Research, 20: (in press).


Cite as: http://hdl.handle.net/21.11116/0000-0004-62DC-6
Abstract
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.