Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport
This work addresses the scalability problem in Optimal Transport for researchers and practitioners in fields like computer vision, though it is incremental as it builds on existing mini-batch methods.
The paper tackles the computational challenge of Optimal Transport for large datasets by introducing novel upper and lower bounds derived from mini-batch OT problems, showing trade-offs between computational budget and bound tightness in experiments.
Optimal Transport (OT) is a fundamental tool for comparing probability distributions, but its exact computation remains prohibitive for large datasets. In this work, we introduce novel families of upper and lower bounds for the OT problem constructed by aggregating solutions of mini-batch OT problems. The upper bound family contains traditional mini-batch averaging at one extreme and a tight bound found by optimal coupling of mini-batches at the other. In between these extremes, we propose various methods to construct bounds based on a fixed computational budget. Through various experiments, we explore the trade-off between computational budget and bound tightness and show the usefulness of these bounds in computer vision applications.