Submodular Framework for Structured-Sparse Optimal Transport
This work addresses the need for efficient and robust transport plans in machine learning applications, though it appears incremental by building on existing unbalanced optimal transport frameworks.
The paper tackles the problem of learning structured-sparse transport plans in unbalanced optimal transport by proposing novel sparsity-constrained formulations and efficient greedy algorithms, showing that these algorithms select diverse support sets and are effective in various applications.
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.