  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.
