mlsanityData to 7 Oct 2026

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

arXiv 2210.13630 ↗First posted 24 Oct 2022cs.LG cs.IT math.ITcited by 1

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 27 of its 55 references that are in the map. First posted on arXiv 24 Oct 2022.

Builds on

27 of 55 references.

References · 27

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  2. 2018Computational Optimal Transportcited by 765
  3. 2015Optimal Transport for Domain Adaptationcited by 457
  4. 2017Learning Generative Models with Sinkhorn Divergencescited by 310
  5. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 219
  6. 2021Unbalanced minibatch Optimal Transport; applications to Domain Adaptationcited by 123
  7. 2018Improving GANs Using Optimal Transportcited by 122
  8. 2019Statistical bounds for entropic optimal transport: sample complexity and the central limit theoremcited by 85
  9. 2017Smooth and Sparse Optimal Transportcited by 83
  10. 2019Learning with minibatch Wasserstein : asymptotic and gradient propertiescited by 83
  11. 2017Sliced Wasserstein Kernel for Persistence Diagramscited by 77
  12. 2021Low-Rank Sinkhorn Factorizationcited by 66
15 more
  1. 2015Sliced Wasserstein Kernels for Probability Distributionscited by 64
  2. 2021Minibatch optimal transport distances; analysis and applicationscited by 62
  3. 2021Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costscited by 61
  4. 2019Tree-Sliced Variants of Wasserstein Distancescited by 54
  5. 2019Hierarchical Optimal Transport for Document Representationcited by 53
  6. 2018Statistical Optimal Transport via Factored Couplingscited by 38
  7. 2019Validated Variational Inference via Practical Posterior Error Boundscited by 26
  8. 2019Scalable Nearest Neighbor Search for Optimal Transportcited by 25
  9. 2020Making transport more robust and interpretable by moving data through a small number of anchor pointscited by 18
  10. 2020Fast and Robust Comparison of Probability Measures in Heterogeneous Spacescited by 17
  11. 2020Polynomial-time algorithms for Multimarginal Optimal Transport problems with structurecited by 15
  12. 2021On Transportation of Mini-batches: A Hierarchical Approachcited by 15
  13. 2022Hierarchical Optimal Transport for Comparing Histopathology Datasetscited by 6
  14. 2021New Streaming Algorithms for High Dimensional EMD and MSTcited by 5
  15. 2021Bounding Wasserstein distance with couplingscited by 5

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.

  1. 2023Scalable Optimal Transport Methods in Machine Learning: A Contemporary Surveycited by 27