Submodular framework for structured-sparse optimal transport

Piyushi Manupriya, Pratik Jawanpuria, Karthik S. Gurumoorthy, Sakethanath Jagarlapudi, Bamdev Mishra
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:34630-34653, 2024.

Abstract

Unbalanced optimal transport (UOT) has recently gained much attention due to its flexible framework for handling un-normalized measures and its robustness properties. In this work, we explore learning (structured) sparse transport plans in the UOT setting, i.e., transport plans have an upper bound on the number of non-sparse entries in each column (structured sparse pattern) or in the whole plan (general sparse pattern). We propose novel sparsity-constrained UOT formulations building on the recently explored maximum mean discrepancy based UOT. We show that the proposed optimization problem is equivalent to the maximization of a weakly submodular function over a uniform matroid or a partition matroid. We develop efficient gradient-based discrete greedy algorithms and provide the corresponding theoretical guarantees. Empirically, we observe that our proposed greedy algorithms select a diverse support set and we illustrate the efficacy of the proposed approach in various applications.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-manupriya24a, title = {Submodular framework for structured-sparse optimal transport}, author = {Manupriya, Piyushi and Jawanpuria, Pratik and Gurumoorthy, Karthik S. and Jagarlapudi, Sakethanath and Mishra, Bamdev}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {34630--34653}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/manupriya24a/manupriya24a.pdf}, url = {https://proceedings.mlr.press/v235/manupriya24a.html}, abstract = {Unbalanced optimal transport (UOT) has recently gained much attention due to its flexible framework for handling un-normalized measures and its robustness properties. In this work, we explore learning (structured) sparse transport plans in the UOT setting, i.e., transport plans have an upper bound on the number of non-sparse entries in each column (structured sparse pattern) or in the whole plan (general sparse pattern). We propose novel sparsity-constrained UOT formulations building on the recently explored maximum mean discrepancy based UOT. We show that the proposed optimization problem is equivalent to the maximization of a weakly submodular function over a uniform matroid or a partition matroid. We develop efficient gradient-based discrete greedy algorithms and provide the corresponding theoretical guarantees. Empirically, we observe that our proposed greedy algorithms select a diverse support set and we illustrate the efficacy of the proposed approach in various applications.} }
Endnote
%0 Conference Paper %T Submodular framework for structured-sparse optimal transport %A Piyushi Manupriya %A Pratik Jawanpuria %A Karthik S. Gurumoorthy %A Sakethanath Jagarlapudi %A Bamdev Mishra %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-manupriya24a %I PMLR %P 34630--34653 %U https://proceedings.mlr.press/v235/manupriya24a.html %V 235 %X Unbalanced optimal transport (UOT) has recently gained much attention due to its flexible framework for handling un-normalized measures and its robustness properties. In this work, we explore learning (structured) sparse transport plans in the UOT setting, i.e., transport plans have an upper bound on the number of non-sparse entries in each column (structured sparse pattern) or in the whole plan (general sparse pattern). We propose novel sparsity-constrained UOT formulations building on the recently explored maximum mean discrepancy based UOT. We show that the proposed optimization problem is equivalent to the maximization of a weakly submodular function over a uniform matroid or a partition matroid. We develop efficient gradient-based discrete greedy algorithms and provide the corresponding theoretical guarantees. Empirically, we observe that our proposed greedy algorithms select a diverse support set and we illustrate the efficacy of the proposed approach in various applications.
APA
Manupriya, P., Jawanpuria, P., Gurumoorthy, K.S., Jagarlapudi, S. & Mishra, B.. (2024). Submodular framework for structured-sparse optimal transport. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:34630-34653 Available from https://proceedings.mlr.press/v235/manupriya24a.html.

Related Material