# Submodular Framework for Structured-Sparse Optimal Transport

arXiv: https://arxiv.org/abs/2406.04914 · HTML: https://mlsanity.com/paper/2406.04914/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 58 references that are in the map.
- First posted on arXiv 7 Jun 2024.

## Builds on (most cited first, 30 of 37)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Learning Factored Representations in a Deep Mixture of Experts](https://mlsanity.com/paper/1312.4314/) (2013)
- [MMD GAN: Towards Deeper Understanding of Moment Matching Network](https://mlsanity.com/paper/1705.08584/) (2017)
- [Unified Scaling Laws for Routed Language Models](https://mlsanity.com/paper/2202.01169/) (2022)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [SimAlign: High Quality Word Alignments without Parallel Training Data using Static and Contextualized Embeddings](https://mlsanity.com/paper/2004.08728/) (2020)
- [Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures](https://mlsanity.com/paper/1508.07941/) (2015)
- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Learning with minibatch Wasserstein : asymptotic and gradient properties](https://mlsanity.com/paper/1910.04091/) (2019)
- [Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation](https://mlsanity.com/paper/2010.05862/) (2020)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [Multi-Hop Paragraph Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/1906.06606/) (2019)
- [Sparsity-Constrained Optimal Transport](https://mlsanity.com/paper/2209.15466/) (2022)
- [Structured Optimal Transport](https://mlsanity.com/paper/1712.06199/) (2017)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Rationalizing Text Matching: Learning Sparse Alignments via Optimal Transport](https://mlsanity.com/paper/2005.13111/) (2020)
- [Quadratically-Regularized Optimal Transport on Graphs](https://mlsanity.com/paper/1704.08200/) (2017)
- [On Transportation of Mini-batches: A Hierarchical Approach](https://mlsanity.com/paper/2102.05912/) (2021)
- [QA-Align: Representing Cross-Text Content Overlap by Aligning Question-Answer Propositions](https://mlsanity.com/paper/2109.12655/) (2021)
- [Tsallis Regularized Optimal Transport and Ecological Inference](https://mlsanity.com/paper/1609.04495/) (2016)
- [Geometry-aware Domain Adaptation for Unsupervised Alignment of Word Embeddings](https://mlsanity.com/paper/2004.08243/) (2020)
- [Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?](https://mlsanity.com/paper/1707.04347/) (2017)
- [SPOT: A framework for selection of prototypes using optimal transport](https://mlsanity.com/paper/2103.10159/) (2021)

## Built on by (most cited first, 5 of 5)

- [A Riemannian Approach to Ground Metric Learning for Optimal Transport](https://mlsanity.com/paper/2409.10085/) (2024)
- [A Riemannian Approach to Low-Rank Optimal Transport](https://mlsanity.com/paper/2606.12120/) (2026)
- [Optimal Transport under Group Fairness Constraints](https://mlsanity.com/paper/2601.07144/) (2026)
- [Minibatch Selection for Language Models via Partition Matroid Constrained Gradient Matching](https://mlsanity.com/paper/2606.07954/) (2026)
- [Probabilistic Multi-Source Data Selection via Learnable Categorical Priors: Variance Reduction and Guaranteed Derandomization](https://mlsanity.com/paper/2610.14942/) (2026)

## Abstract (arXiv)

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.