Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
Peter Matthew Jacobs, Jeff M. Phillips · 2026
Read Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation by Peter Matthew Jacobs, Jeff M. Phillips (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-20122.txt.
Description
Peter Matthew Jacobs and Jeff Phillips study the runtime of squared Wasserstein distance estimation. Exact computation scales poorly with sample size and precision in two or three dimensions. They estimate the distance between smooth measures from samples, up to epsilon additive error in expectation. Their sample-sketch-solve method compresses samples with a Cartesian grid sketch without raising asymptotic error, enabling faster exact algorithms. For Hölder distributions they reach near-optimal runtimes, including optimal order epsilon to the minus two for dimension two when smoothness exceeds one half.
Catalog record
| CREATOR | Peter Matthew Jacobs, Jeff M. Phillips |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46531 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.20122