Quantization-based Bounds on the Wasserstein Metric
This addresses the efficiency problem for machine learning practitioners using Wasserstein metrics in applications like generative modeling, offering an incremental improvement over existing approximation methods.
The paper tackles the computational cost of the Wasserstein metric by developing a quantization-based method that provides strict upper and lower bounds, achieving a 10x-100x speedup over entropy-regularized optimal transport with approximation errors below 2% on the DOTmark benchmark.
The Wasserstein metric has become increasingly important in many machine learning applications such as generative modeling, image retrieval and domain adaptation. Despite its appeal, it is often too costly to compute. This has motivated approximation methods like entropy-regularized optimal transport, downsampling, and subsampling, which trade accuracy for computational efficiency. In this paper, we consider the challenge of computing efficient approximations to the Wasserstein metric that also serve as strict upper or lower bounds. Focusing on discrete measures on regular grids, our approach involves formulating and exactly solving a Kantorovich problem on a coarse grid using a quantized measure and specially designed cost matrix, followed by an upscaling and correction stage. This is done either in the primal or dual space to obtain valid upper and lower bounds on the Wasserstein metric of the full-resolution inputs. We evaluate our methods on the DOTmark optimal transport images benchmark, demonstrating a 10x-100x speedup compared to entropy-regularized OT while keeping the approximation error below 2%.