# Sparsity-Constrained Optimal Transport

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 59 references that are in the map.
- First posted on arXiv 30 Sep 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding](https://mlsanity.com/paper/2006.16668/) (2020)
- [SuperGlue: Learning Feature Matching with Graph Neural Networks](https://mlsanity.com/paper/1911.11763/) (2019)
- [Revisiting Unreasonable Effectiveness of Data in Deep Learning Era](https://mlsanity.com/paper/1707.02968/) (2017)
- [Scaling Vision with Sparse Mixture of Experts](https://mlsanity.com/paper/2106.05974/) (2021)
- [BASE Layers: Simplifying Training of Large, Sparse Models](https://mlsanity.com/paper/2103.16716/) (2021)
- [Unified Scaling Laws for Routed Language Models](https://mlsanity.com/paper/2202.01169/) (2022)
- [Hash Layers For Large Sparse Models](https://mlsanity.com/paper/2106.04426/) (2021)
- [Multimodal Contrastive Learning with LIMoE: the Language-Image Mixture of Experts](https://mlsanity.com/paper/2206.02770/) (2022)
- [A Review of Sparse Expert Models in Deep Learning](https://mlsanity.com/paper/2209.01667/) (2022)
- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Top-k Multiclass SVM](https://mlsanity.com/paper/1511.06683/) (2015)
- [Meta Optimal Transport](https://mlsanity.com/paper/2206.05262/) (2022)
- [SpeechMoE2: Mixture-of-Experts Model with Improved Routing](https://mlsanity.com/paper/2111.11831/) (2021)
- [Regularized Optimal Transport and the Rot Mover's Distance](https://mlsanity.com/paper/1610.06447/) (2016)
- [Differentiable Deep Clustering with Cluster Size Constraints](https://mlsanity.com/paper/1910.09036/) (2019)
- [Efficient Marginalization of Discrete and Structured Latent Variables via Sparsity](https://mlsanity.com/paper/2007.01919/) (2020)
- [TPU-KNN: K Nearest Neighbor Search at Peak FLOP/s](https://mlsanity.com/paper/2206.14286/) (2022)
- [Quadratically regularized optimal transport](https://mlsanity.com/paper/1903.01112/) (2019)
- [Convergence of a Newton algorithm for semi-discrete optimal transport](https://mlsanity.com/paper/1603.05579/) (2016)
- [Unbiased Gradient Estimation with Balanced Assignments for Mixtures of Experts](https://mlsanity.com/paper/2109.11817/) (2021)
- [New Perspectives on k-Support and Cluster Norms](https://mlsanity.com/paper/1512.08204/) (2015)
- [A Smoother Way to Train Structured Prediction Models](https://mlsanity.com/paper/1902.03228/) (2019)
- [Wasserstein k-means with sparse simplex projection](https://mlsanity.com/paper/2011.12542/) (2020)

## Built on by (most cited first, 30 of 32)

- [From Sparse to Soft Mixtures of Experts](https://mlsanity.com/paper/2308.00951/) (2023)
- [Projecting Assumptions: The Duality Between Sparse Autoencoders and Concept Geometry](https://mlsanity.com/paper/2503.01822/) (2025)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Routers in Vision Mixture of Experts: An Empirical Study](https://mlsanity.com/paper/2401.15969/) (2024)
- [Monge, Bregman and Occam: Interpretable Optimal Transport in High-Dimensions with Feature-Sparse Maps](https://mlsanity.com/paper/2302.04065/) (2023)
- [Accurate Neural Network Pruning Requires Rethinking Sparse Optimization](https://mlsanity.com/paper/2308.02060/) (2023)
- [Structured Transforms Across Spaces with Cost-Regularized Optimal Transport](https://mlsanity.com/paper/2311.05788/) (2023)
- [Tight Clusters Make Specialized Experts](https://mlsanity.com/paper/2502.15315/) (2025)
- [Many-Objective Multi-Solution Transport](https://mlsanity.com/paper/2403.04099/) (2024)
- [Submodular Framework for Structured-Sparse Optimal Transport](https://mlsanity.com/paper/2406.04914/) (2024)
- [Plasticity-Aware Mixture of Experts for Learning Under QoE Shifts in Adaptive Video Streaming](https://mlsanity.com/paper/2504.09906/) (2025)
- [Improving Routing in Sparse Mixture of Experts with Graph of Tokens](https://mlsanity.com/paper/2505.00792/) (2025)
- [SoftMoE: Soft Differentiable Routing for Mixture-of-Experts in LLMs](https://mlsanity.com/paper/2606.17952/) (2026)
- [Bringing regularized optimal transport to lightspeed: a splitting method adapted for GPUs](https://mlsanity.com/paper/2305.18483/) (2023)
- [Optimal Transport with Tempered Exponential Measures](https://mlsanity.com/paper/2309.04015/) (2023)
- [Unleashing the Power of Meta-tuning for Few-shot Generalization Through Sparse Interpolated Experts](https://mlsanity.com/paper/2403.08477/) (2024)
- [A Riemannian Approach to Ground Metric Learning for Optimal Transport](https://mlsanity.com/paper/2409.10085/) (2024)
- [When Graph Neural Networks Meet Dynamic Mode Decomposition](https://mlsanity.com/paper/2410.05593/) (2024)
- [Modeling Expert Interactions in Sparse Mixture of Experts via Graph Structures](https://mlsanity.com/paper/2510.16411/) (2025)
- [Selective Sinkhorn Routing for Improved Sparse Mixture of Experts](https://mlsanity.com/paper/2511.08972/) (2025)
- [Sliced-Regularized Optimal Transport](https://mlsanity.com/paper/2604.23944/) (2026)
- [Displacement-Sparse Neural Optimal Transport](https://mlsanity.com/paper/2502.01889/) (2025)
- [Sparse Partial Optimal Transport via Quadratic Regularization](https://mlsanity.com/paper/2508.08476/) (2025)
- [High-Rate Phase Association with Travel Time Neural Fields](https://mlsanity.com/paper/2307.07572/) (2023)
- [Sparse Domain Transfer via Elastic Net Regularization](https://mlsanity.com/paper/2405.07489/) (2024)
- [Many-to-Many Matching via Sparsity Controlled Optimal Transport](https://mlsanity.com/paper/2503.24204/) (2025)
- [Optimal Transport under Group Fairness Constraints](https://mlsanity.com/paper/2601.07144/) (2026)
- [Multi-Domain Learning with Global Expert Mapping](https://mlsanity.com/paper/2604.18842/) (2026)
- [HMR-Net: Hierarchical Modular Routing for Cross-Domain Object Detection in Aerial Images](https://mlsanity.com/paper/2604.18866/) (2026)
- [Take It or Leave It: Intent-Controlled Partial Optimal Transport](https://mlsanity.com/paper/2605.20030/) (2026)

## Abstract (arXiv)

Regularized optimal transport (OT) is now increasingly used as a loss or as a matching layer in neural networks. Entropy-regularized OT can be computed using the Sinkhorn algorithm but it leads to fully-dense transportation plans, meaning that all sources are (fractionally) matched with all targets. To address this issue, several works have investigated quadratic regularization instead. This regularization preserves sparsity and leads to unconstrained and smooth (semi) dual objectives, that can be solved with off-the-shelf gradient methods. Unfortunately, quadratic regularization does not give direct control over the cardinality (number of nonzeros) of the transportation plan. We propose in this paper a new approach for OT with explicit cardinality constraints on the transportation plan. Our work is motivated by an application to sparse mixture of experts, where OT can be used to match input tokens such as image patches with expert models such as neural networks. Cardinality constraints ensure that at most k tokens are matched with an expert, which is crucial for computational performance reasons. Despite the nonconvexity of cardinality constraints, we show that the corresponding (semi) dual problems are tractable and can be solved with first-order gradient methods. Our method can be thought as a middle ground between unregularized OT (recovered in the limit case k=1) and quadratically-regularized OT (recovered when k is large enough). The smoothness of the objectives increases as k increases, giving rise to a trade-off between convergence speed and sparsity of the optimal plan.