Research map / Learning theory and algorithms / Optimal transport
Submodular framework for structured-sparse optimal transport
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes sparsity-constrained MMD-based unbalanced optimal transport (general and column-wise sparse plans), shows the support-set objective is weakly submodular over uniform/partition matroids, and gives gradient-based greedy (OMP-style) algorithms with guarantees.
Problem
Learning sparse transport plans in unbalanced optimal transport, where the plan has a bound on non-zero entries overall or per column; the resulting problem is non-convex and non-smooth.
Approach
Reformulates the cardinality/column-sparse constrained MMD-UOT as maximizing a weakly submodular set function over a uniform or partition matroid, then applies stochastic and matroid-constrained OMP-style greedy selection using gradients of the convex UOT subproblem, plus a duality-gap analysis.
Key results
- On the SPFD topology task with l=250, proposed GenSparseUOT reaches expected profit 0.293 versus 0.044 for GSOT.
- On the Wiki word alignment test split, the proposed method reaches 49.14 null accuracy, roughly at par with BOT (48.95) and above MMD-UOT (41.35).
- In the duality gap comparison, the proposed solver achieves gaps below 1e-10 in some settings and at least three times lower gaps than SCOT in the reported table.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GenSparseUOT instead of GSOT | SPFD topology design · SPFD, l=100, 175, and 250 | expected profit: l=100: 0.014 -> 0.167; l=175: 0.031 -> 0.240; l=250: 0.044 -> 0.293 | Helped |
| Use GenSparseUOT instead of BOT | Monolingual word alignment · Wiki test, null alignments | accuracy: 48.95 -> 49.14 | Helped |
| Use GenSparseUOT instead of BOT | Monolingual word alignment · Wiki test, null alignments | F1: 80.05 -> 79.92 | Hurt |
| Use GenSparseUOT instead of BOT | Monolingual word alignment · Wiki test, total alignments | accuracy: 47.05 -> 48.00 | Helped |
| Use GenSparseUOT instead of BOT | Monolingual word alignment · Wiki test, total alignments | F1: 94.96 -> 94.79 | Hurt |
| Use ColSparseUOT instead of SCOT | ResNet18 SMoE · CIFAR-10 vs CIFAR-10-rotate test | accuracy: λ₁=0.1: 77.96 -> 95.56; λ₁=10: 90.56 -> 85.18; λ₁=1000: 56.48 -> 90.54 | Mixed |
| Use the proposed solver instead of SCOT | Column-wise sparse UOT optimization · CIFAR-10 batches, all reported (λ₁, λ₂) settings | duality gap: (0.1,0.1): 0.00232 -> <10^{-10}; (1,0.1): 0.19111 -> 0.01911; (10,0.1): 2.21029 -> 0.64896; (0.1,1): 0.00114 -> <10^{-10 | Helped |
Surprising findings
- On the Wiki word alignment task the proposed method is only at par with the simple BOT baseline rather than clearly better.
- On CIFAR SMoE the default Top-1 MoE reaches higher accuracy (95.91) than the proposed balanced variant, reflecting an accuracy-balance trade-off.
Limitations
- Greedy guarantees depend on weak submodularity ratio u_{2K}/U_1, which is not tight and is hard to compute in practice.
- Only weak duality holds for the non-convex sparse problem, so duality gap is a heuristic optimality indicator.
- Experiments are limited to small-scale settings (e.g., m=n=100, toy and small CIFAR SMoE) and the SPFD comparison omits other sparse baselines.
Experimental setup
Datasets: CIFAR-10 CIFAR-10-rotate Wiki aligned sentences (sure alignments)
Benchmarks: Wiki word alignment dataset CIFAR-10 vs CIFAR-10-rotate SMoE classification synthetic SPFD network topology data
Metrics: expected profit accuracy F1 duality gap expert load balance
Baselines: GSOT SSOT MMD-UOT BOT POT KL-UOT SCOT epsilon-OT gating
Builds on: MMD-UOT SCOT orthogonal matching pursuit stochastic greedy
Closest papers by meaning
- Optimal Transport with Tempered Exponential Measures (AAAI 2024 · similarity 0.89)
- Expected Sliced Transport Plans (ICLR 2025 · similarity 0.87)
- Sparsistency for inverse optimal transport (ICLR 2024 · similarity 0.87)
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.87)
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.86)
- Unsupervised Learning for Optimal Transport plan prediction between unbalanced graphs (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.