Improving Approximate Optimal Transport Distances using Quantization

Abstract

Optimal transport (OT) is a popular tool in machine learning to compare probability measures geometrically, but it comes with substantial computational burden. Linear programming algorithms for computing OT distances scale cubically in the size of the input, making OT impractical in the large-sample regime. We introduce a practical algorithm, which relies on a quantization step, to estimate OT distances between measures given cheap sample access. We also provide a variant of our algorithm to improve the performance of approximate solvers, focusing on those for entropy-regularized transport. We give theoretical guarantees on the benefits of this quantization step and display experiments showing that it behaves well in practice, providing a practical approximation algorithm that can be used as a drop-in replacement for existing OT estimators.

arXiv commentPublished in the proceedings of the Conference on Uncertainty in Artificial Intelligence 2021 (UAI)

References in corpus (6)

• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Sample Complexity of Sinkhorn divergences
• Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
• DOTmark - A Benchmark for Discrete Optimal Transport
• Learning Probability Measures with respect to Optimal Transport Metrics
• Gaussian-Smooth Optimal Transport: Metric Structure and Statistical Efficiency

Cited by in corpus (2)

• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Discrepancy-based Inference for Intractable Generative Models using Quasi-Monte Carlo