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.
Methods: Tractable Cardinality Constraints
The authors propose adding a cardinality constraint ($\|t\|_0 \leq k$) to the columns of the transportation plan.
- 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.
- 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.
- 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.
- 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.
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