Sparsity-Constrained Optimal Transport

Tianlin Liu, Joan Puigcerver, Mathieu Blondel

Introduction

This paper introduces a novel approach to Optimal Transport (OT) that allows for explicit control over the number of non-zero entries (cardinality) in the transportation plan. By formulating OT with non-convex cardinality constraints, the authors provide a "middle ground" between dense entropic OT and quadratically regularized OT, proving that the resulting optimization problems remain tractable and highly effective for scaling sparse Mixture of Experts (MoE) models.

The Problem: Dense vs. Sparse Transport

Optimal Transport is a powerful framework for matching distributions, but it faces a practical dilemma in machine learning: standard OT is computationally heavy. To solve this, researchers often use Entropy-regularized OT (the Sinkhorn algorithm), which is fast and differentiable but results in "fully dense" plans—meaning every source point is fractionally matched to every target point.

In many applications, like Sparse Mixture of Experts (MoE), density is a deal-breaker. In MoE, we want to route an input "token" (like an image patch) to only a few "expert" neural networks to save computation. While Quadratic regularization promotes sparsity, it doesn't give you a "knob" to turn to guarantee exactly how many experts ($k$) a token should see. This paper fills that gap by providing a framework for OT with explicit $k$-sparsity constraints.

Comparison of transportation plans across different OT regularization methods.

Methods: Tractable Cardinality Constraints

The authors propose adding a cardinality constraint ($\|t\|_0 \leq k$) to the columns of the transportation plan.

  1. Non-convex Regularization: They define a regularization function $\Omega$ that combines a squared 2-norm (for smoothness) with an indicator function that is zero if the vector is $k$-sparse and infinite otherwise.
  2. Tractable Duals: Although the cardinality constraint is non-convex, the authors leverage convex analysis to show that the dual and semi-dual formulations remain concave maximization problems. This means they can be solved to global optimality using standard first-order methods like LBFGS or ADAM.
  3. The $k$-Support Norm Connection: A key theoretical contribution is showing that their approach is equivalent to using the squared $k$-support norm in the primal objective. This norm is the tightest convex relaxation of the sparsity constraint.
  4. Plan Recovery: They provide a way to recover the optimal transportation plan from the dual variables using a "top-$k$ sparsemax" operation.

Key Insights: The Smoothness-Sparsity Trade-off

A fascinating discovery in this work is the relationship between the chosen sparsity level $k$ and the smoothness of the optimization landscape. The smoothness of the dual objective increases as $k$ increases.

The dual objective becomes smoother as the sparsity parameter k increases.

This creates a fundamental trade-off: a larger $k$ (less sparsity) leads to faster convergence of the optimization algorithm, while a smaller $k$ provides the strict sparsity needed for computational efficiency in the final model. The method acts as a bridge: when $k=1$, it recovers unregularized OT (maximally sparse), and when $k$ is large enough, it recovers standard quadratically-regularized OT.

Furthermore, unlike simple "Top-K" routing (which is greedy and can lead to expert imbalance), this OT-based router considers global constraints (expert capacity) while maintaining the strict $k$-sparsity required by hardware buffers.

Experimental Validation and Results

The authors validate their method across several domains, including synthetic data (1D/2D Gaussians), color transfer, global supply-demand mapping, and clustering on MNIST.

Their primary benchmark, however, is Large-Scale Vision (V-MoE). They pre-train Vision Mixture of Experts models on JFT-300M (305 million images) and evaluate 10-shot transfer performance on ImageNet.

  • V-MoE Performance: The sparsity-constrained OT router consistently outperformed both the standard Top-K router and the Sinkhorn-based (S-BASE) router. For example, on V-MoE B/16, it achieved 72.76% 10-shot accuracy on ImageNet, compared to 72.12% for TopK.
  • Convergence: LBFGS proved to be a robust solver, generally converging faster in terms of iterations than ADAM and requiring no hyperparameter tuning for the learning rate.
  • Interpretability: In the global supply-demand task, the sparsity constraint produced much clearer, more interpretable "routes" compared to the dense plans produced by entropy-regularized OT.

Limitations and Future Work

While the dual is tractable, solving an iterative optimization problem (LBFGS/ADAM) inside every forward pass of a neural network introduces computational overhead compared to a simple greedy Top-K operation. The authors note their router is slightly slower than baselines. Additionally, recovering the transportation plan becomes mathematically complex when there are "ties" in the top-$k$ values of the dual variables, requiring the solution of a system of linear equations. Future work could explore using approximated versions of the top-$k$ function to further accelerate the routing process for extremely large models.

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