English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Optimal transport: Fast probabilistic approximation with exact solvers.

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).

Item is

Files

show Files
hide Files
:
3149995.pdf (Preprint), 694KB
Name:
3149995.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Sommerfeld, M., Author
Schrieber, J., Author
Zemel, Y., Author
Munk, A.1, Author           
Affiliations:
1Research Group of Statistical Inverse-Problems in Biophysics, MPI for biophysical chemistry, Max Planck Society, ou_1113580              

Content

show
hide
Free keywords: computational vs statistical accuracy; covering numbers; empirical optimal transport; resampling; risk bounds; spanning tree; Wasserstein distance
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2019-07-05
 Publication Status: Published online
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: arXiv: arxiv.org/abs/1802.05570
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: The Journal of Machine Learning Research
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 20 Sequence Number: (in press) Start / End Page: - Identifier: -