MMD-Regularized Unbalanced Optimal Transport
Abstract: We study the unbalanced optimal transport (UOT) problem, where the marginal constraints are enforced using Maximum Mean Discrepancy (MMD) regularization. Our work is motivated by the observation that the literature on UOT is focused on regularization based on $\phi$-divergence (e.g., KL divergence). Despite the popularity of MMD, its role as a regularizer in the context of UOT seems less understood. We begin by deriving a specific dual of MMD-regularized UOT (MMD-UOT), which helps us prove several useful properties. One interesting outcome of this duality result is that MMD-UOT induces novel metrics, which not only lift the ground metric like the Wasserstein but are also sample-wise efficient to estimate like the MMD. Further, for real-world applications involving non-discrete measures, we present an estimator for the transport plan that is supported only on the given ($m$) samples. Under certain conditions, we prove that the estimation error with this finitely-supported transport plan is also $\mathcal{O}(1/\sqrt{m})$. As far as we know, such error bounds that are free from the curse of dimensionality are not known for $\phi$-divergence regularized UOT. Finally, we discuss how the proposed estimator can be computed efficiently using accelerated gradient descent. Our experiments show that MMD-UOT consistently outperforms popular baselines, including KL-regularized UOT and MMD, in diverse machine learning applications.
Submission Length: Long submission (more than 12 pages of main content)
Changes Since Last Submission: - Switched to camera-ready format & de-anonymized the paper.
- Added subsection B.9.1 in the Appendix as an additional discussion on Theorem 4.10.
- Added link to code & corrected some typos.
- The Supplementary section "Comparison with WAE" has been moved (as is) from Appendix C.6 to Appendix B.18 (of theory results).
Video: https://youtu.be/FSJ4_GfLhHo
Code: https://github.com/Piyushi-0/MMD-reg-OT
Supplementary Material: zip
Assigned Action Editor: ~Benjamin_Guedj1
License: Creative Commons Attribution 4.0 International (CC BY 4.0)
Submission Number: 1570
Loading