Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport

Optimal Transport (OT) distances, in particular the Wasserstein distance, have become a popular tool in machine learning for tasks ranging from domain adaptation (Courty et al., 2017) to generative modeling (Genevay et al., 2018; Salimans et al., 2018). From among its many desirable properties, we highlight that OT provides a principled and general approach to lift a metric between samples into one between distributions, is underpinned by a mature theory (Villani, 2008, 2003), and has a well-understood sample complexity (Genevay et al., 2019; Mena and Weed, 2019). Historically, a primary barrier to the wider adoption of OT in machine learning and other data-intensive fields has been its computational cost. In the classic formulation by Kantorovich (1942), the discrete OT problem is a linear programming (LP) problem with cubic complexity and quadratic memory footprint, prohibitive for all but the smallest datasets. Over the past decade, there has been considerable progress towards scaling up the computation of OT, typically by settling for an approximate solution by solving an entropy-regularized problem instead (Cuturi, 2013).