Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances
This work addresses the computational bottleneck for researchers and practitioners using optimal transportation in machine learning, offering a faster alternative with practical gains.
The authors tackled the computational inefficiency of optimal transportation distances for histograms by introducing a maximum-entropy perspective with entropic regularization, resulting in a new distance that can be computed orders of magnitude faster using Sinkhorn-Knopp's algorithm and showing improved performance on the MNIST benchmark.
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.