Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport. (arXiv:2210.13630v1 [cs.LG])

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 …

arxiv budget transport