Improving Approximate Optimal Transport Distances using Quantization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
QuantizationSimilar Papers 제목 키워드 기반
Multiscale Strategies for Computing Optimal Transport
This paper presents a multiscale approach to efficiently compute approximate optimal transport plans between point sets. It is particularly well-suited for point sets that are in high-dimensions, but are close to being i…
AnatomyNear-linear time approximation algorithms for optimal transport via Sinkhorn iteration
Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empi…
BIG-bench Machine LearningPT$\mathrm{L}^{p}$: Partial Transport $\mathrm{L}^{p}$ Distances
Optimal transport and its related problems, including optimal partial transport, have proven to be valuable tools in machine learning for computing meaningful distances between probability or positive measures. This succ…
Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances
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, the…
RetrievalLinear Spherical Sliced Optimal Transport: A Fast Metric for Comparing Spherical Data
Efficient comparison of spherical probability distributions becomes important in fields such as computer vision, geosciences, and medicine. Sliced optimal transport distances, such as spherical and stereographic spherica…
3D Point Cloud InterpolationComputational Efficiency