Sparsity-Constrained Optimal Transport

Tianlin Liu, Joan Puigcerver, Mathieu Blondel

Abstract

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.

Introduction

Optimal Transport (OT) is a powerful framework for matching distributions, but its application in machine learning often faces a "density" problem. Standard entropy-regularized OT, typically solved via the Sinkhorn algorithm, results in fully dense transportation plans where every source point is fractionally matched to every target point. This lack of sparsity is both computationally expensive and often undesirable for interpretability.

While quadratic regularization has been proposed to promote sparsity, it lacks direct control over the exact number of non-zero matches (cardinality). In domains like Sparse Mixture of Experts (MoE), practitioners require a strict limit: each input token should be processed by at most $k$ experts to maintain predictable computational costs. This paper introduces a novel OT framework that imposes non-convex cardinality constraints while remaining computationally tractable through a dual formulation.

The Sparsity-Constrained Approach

The core of the proposed method is a constraint on each column of the transportation plan $T$, ensuring it has at most $k$ non-zero elements ($||t_j||_0 \leq k$). This approach acts as a bridge between two extremes: when $k=1$, it recovers the maximal sparsity of unregularized OT; as $k$ increases, it approaches the behavior of quadratically-regularized OT.

Comparison of transportation plans and their sparsity patterns across different regularization schemes. The proposed sparsity-constrained method (right) allows for explicit control over the number of non-zero entries per column.

Key technical insights include:

  • Tractable Duals: Despite the non-convexity of the sparsity constraint, the resulting dual and semi-dual objectives are concave maximization problems, allowing for global optimality via first-order methods like LBFGS or ADAM.
  • $k$-Sparse Projections: The gradients involve projections onto the $k$-sparse simplex, which can be efficiently computed using a "top-$k$" operation.
  • Theoretical Foundation: The method is shown to be equivalent to using the squared $k$-support norm as a regularizer, providing a convex relaxation of the $\ell_0$ constraint.

Smoothness and Convergence Properties

A critical finding is the relationship between the cardinality constraint $k$ and the smoothness of the optimization landscape. As $k$ increases, the dual objective becomes smoother, facilitating faster convergence at the cost of reduced sparsity in the final plan.

Visualization of the dual objective surfaces for $k=1, 2, 3$. Increasing $k$ leads to smoother objectives, illustrating the trade-off between plan sparsity and optimization ease.

This trade-off allows users to tune the "softness" of the matching using an intuitive integer $k$ rather than a continuous penalty parameter alone. Experiments show that LBFGS is particularly effective for solving these dual objectives, often outperforming ADAM in convergence speed.

Experimental Results

The framework was validated across several diverse tasks:

  • Vision MoE (V-MoE): Using the sparsity-constrained OT as a router in V-MoE architectures on the JFT-300M dataset. It outperformed standard Top-K and Sinkhorn-based routers, achieving 50.29% precision@1 on JFT (compared to 48.86% for Top-K).
  • Balanced Clustering: On the MNIST dataset, the method achieved more balanced clustering (measured by KL divergence from a uniform distribution) than K-Means or other regularized OT variants.
  • Synthetic and Geospatial Data: Visualizations on 2D Gaussian distributions and large-scale supply-demand problems confirmed the method's ability to maintain strict sparsity while satisfying marginal constraints.

Conclusion

Sparsity-constrained OT offers a robust "middle ground" for matching problems requiring explicit control over cardinality. By leveraging dual formulations, the authors demonstrate that non-convex $\ell_0$ constraints can be handled efficiently. While the iterative optimization loop introduces some computational overhead compared to simple Top-K routing, the gains in performance and load balancing make it a compelling choice for modern sparse architectures like Mixture of Experts. Future work may focus on further accelerating the top-$k$ projection steps and automated hyperparameter tuning.

Summary updated

Abstract

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.
BibTeX
@inproceedings{liu2023sparsity,
  author = {Tianlin Liu and Joan Puigcerver and Mathieu Blondel},
  title = {{Sparsity-Constrained Optimal Transport}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=yHY9NbQJ5BP},
}
Figure