Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances
About
Optimal transportation distances are a fundamental family of parameterized distances for histograms. Despite their appealing theoretical properties, excellent performance in retrieval tasks and intuitive formulation, their computation involves the resolution of a linear program whose cost is prohibitive whenever the histograms' dimension exceeds a few hundreds. We propose in this work a new family of optimal transportation distances that look at transportation problems from a maximum-entropy perspective. We smooth the classical optimal transportation problem with an entropic regularization term, and show that the resulting optimum is also a distance which can be computed through Sinkhorn-Knopp's matrix scaling algorithm at a speed that is several orders of magnitude faster than that of transportation solvers. We also report improved performance over classical optimal transportation distances on the MNIST benchmark problem.
Related benchmarks
| Task | Dataset | Result | Rank | |
|---|---|---|---|---|
| Unsupervised Domain Adaptation | Caltech-Office | Accuracy (A → C)76.83 | 20 | |
| Image Generation | MNIST standard (test) | FID43.4 | 13 | |
| Image Generation | Fashion-MNIST standard (test) | FID63.8 | 9 | |
| Image Generation | CelebA downsampled (test) | FID129.5 | 5 | |
| 1-Wasserstein distance computation | noisy-sphere-3 (test) | Time (s)2.591 | 5 | |
| 1-Wasserstein distance computation | noisy-sphere-6 (test) | Computation Time (s)1.986 | 5 | |
| 1-Wasserstein distance computation | ModelNet large (test) | Time (s)239.4 | 5 | |
| 1-Wasserstein distance computation | RNAseq (test) | Computation Time (s)92.153 | 5 | |
| 1-Wasserstein distance computation | uniform (test) | Computation Time (seconds)15.113 | 5 | |
| 1-Wasserstein distance computation | ModelNet small (test) | Time (s)2.074 | 5 |