Optimal Transport (OT) provides a powerful geometric framework for comparing probability distributions. In its classical formulation, finding the optimal transport plan is a linear programming problem. While unregularized OT naturally yields sparse plans—meaning mass is moved along a minimal set of distinct pathways—solving it is computationally expensive, scaling cubically with the number of data points ($O(N^3)$).
The "Sinkhorn revolution" bypassed this computational bottleneck by adding an entropic regularization term to the objective function. This mathematical twist transforms a slow linear program into a strictly convex problem that can be solved in near-linear time ($O(N^2)$) using simple matrix scaling updates. However, this speedup comes at a steep conceptual cost: entropic regularization destroys sparsity.
An entropic penalty forces the resulting transport plan to be strictly dense. Every source point is forced to distribute at least a fraction of its mass to every single target point, resulting in a "blurry" allocation matrix. In many machine learning applications—such as pseudo-labeling, domain adaptation, and resource routing—this lack of sparsity is a fatal flaw. We want sharp, decisive, and interpretable assignments, not a dense fog of infinitesimal connections.
To fix this, a growing body of research focuses on Sparse Optimal Transport: alternative regularization strategies that preserve the computational benefits of smooth optimization while recovering exact zeros in the transport plan.
The Geometry of the Zero Boundary
To understand why entropic regularization fails at sparsity and how other methods succeed, we must look at how these regularizers behave near zero.
Consider an entry $P_{ij}$ in the transport plan matrix, representing the amount of mass sent from source $i$ to target $j$. The entropic regularization penalty is defined as:
$$\Omega_{\text{ent}}(P) = \sum_{i,j} P_{ij} \log P_{ij}$$
If we take the derivative of this penalty with respect to an individual entry $P_{ij}$, we get $\log P_{ij} + 1$. Notice what happens as $P_{ij}$ approaches zero from above:
$$\lim_{P_{ij} \to 0^+} (\log P_{ij} + 1) = -\infty$$
This infinite negative gradient acts as an unyielding physical barrier. The optimization algorithm can never push $P_{ij}$ to zero because the cost of doing so becomes infinitely high. Consequently, every entry in an entropically regularized transport plan is strictly positive ($P_{ij} > 0$).
The Quadratic Alternative
What happens if we swap the entropic penalty for a squared Euclidean ($L_2$) penalty? This approach, known as Quadratically Regularized Optimal Transport (QOT), modifies the objective with:
$$\Omega_{\text{quad}}(P) = \frac{1}{2} \sum_{i,j} P_{ij}^2$$
The derivative of this penalty with respect to $P_{ij}$ is simply $P_{ij}$. As $P_{ij}$ approaches zero, its gradient smoothly approaches zero as well. There is no infinite barrier. As a result, when the optimization path hits the non-negativity constraint ($P_{ij} \geq 0$), it can comfortably rest exactly on the boundary, setting irrelevant transport paths to exactly zero.
As demonstrated by Blondel et al., this primal regularization allows variables to hit the zero-boundary while maintaining differentiability. In a graph setting, Solomon et al. showed that quadratic regularization preserves the underlying network sparsity by allowing exact zero flows on edges. Furthermore, Nutz provided the theoretical guarantee that for sufficiently small regularization parameters, the support of the QOT solution remains strictly localized within a small neighborhood of the original, unregularized Monge map.
The Mathematical Engine: Convex Conjugates and Clipping
The emergence of sparsity can be generalized beyond the quadratic penalty to a wider family of regularizers. The core mechanism relies on how dual optimization variables are mapped back into the primal transport plan.
When solving a regularized OT problem, we typically maximize a dual objective involving potentials. Once the optimal dual potentials are found, the primal transport plan $P$ is reconstructed via the gradient of the convex conjugate of the regularizer, denoted as $\nabla \Omega^*$.
Terjék et al. analyzed this relationship for general $f$-divergences. The primal-dual mapping takes the form:
$$P_{ij} = \nabla \Omega^*( \text{dual terms} )$$
For entropic regularization, the convex conjugate is the exponential function ($\Omega^*(x) = \exp(x)$). Because $\exp(x)$ is strictly positive for all real inputs, the transport plan can never contain a zero.
For regularizers like the $\chi^2$-divergence, triangular discrimination, or the quadratic norm, the convex conjugate behaves like a Rectified Linear Unit (ReLU) or a thresholding operator. When the dual terms drop below a certain threshold, $\nabla \Omega^*$ evaluates to exactly zero. This "clipping" mechanism prunes low-probability connections, naturally generating a sparse transport plan.
Entropic (KL) Mapping: Dual Variables ───> [ Exponential ] ───> Strictly Positive P_ij (Dense)
Sparse (e.g., QOT) Mapping: Dual Variables ───> [ Threshold/ReLU ] ───> Exact Zeros for P_ij (Sparse)
By exploiting this property, Amid et al. introduced the use of Tempered Exponential Measures (based on Tsallis entropy). This formulation provides a continuous mathematical bridge: by tuning a single parameter, researchers can smoothly transition from the completely dense solutions of Shannon entropy to the highly sparse solutions of classical linear programming, all while maintaining near-linear computational complexity.
Structuring the Sparsity
Plain sparsity means having many zeros in the matrix, but in machine learning, we often want those zeros to follow a specific structural pattern.
Group Sparsity and Latent Blocks
In domain adaptation, we want to transport samples from a source domain to a target domain without mixing up their semantic classes. If we use standard entropic OT, mass from a source "dog" image might be fractionally distributed across target "dog", "cat", and "car" images.
To prevent this cross-class blurring, Rahbar et al. proposed a Sum-of-Norms (SON) regularization framework. By applying group-sparsity penalties to the transport plan, the optimization forces transport vectors for different data points to become identical. This naturally discovers latent block structures in the coupling matrix, ensuring that samples are transported together in class-specific clusters without requiring explicit target labels. Similarly, Lindbäck et al. utilized proximal operators to incorporate Group Lasso penalties directly into the transport plan, preserving geometric variation and class boundaries.
Feature Sparsity
Sometimes, the goal is not a sparse allocation matrix between samples, but rather a transport map that is sparse in the feature space. When moving a high-dimensional distribution (e.g., gene expression profiles), we might want the displacement vectors to only change a few coordinates at a time.
Cuturi et al. achieved this by integrating $L_1$ and Elastic Net penalties directly into the cost function of the optimal transport problem. Guided by the proximal operator of the regularizer, the data points are transported along parsimonious trajectories that only modify the most critical features. As mathematically derived by Farnia et al., this sparse domain transfer yields an optimal mapping equivalent to a soft-thresholded gradient of a potential function, allowing models to alter the "style" of an input while leaving unrelated attributes completely untouched.
Enforcing Strict Budgets: Cardinality Constraints
While quadratic and $f$-divergence regularizers promote sparsity, they do not give you explicit control over the exact number of non-zero entries. The final sparsity level depends implicitly on the choice of the regularization parameter, which must be tuned via trial and error.
In hardware-constrained systems, this unpredictability is unacceptable. Consider a sparse Mixture of Experts (MoE) model, where an optimal transport solver routes incoming tokens to a pool of neural network "experts." To satisfy strict memory and compute budgets, each token must be routed to a fixed, maximum number of experts (e.g., exactly $k=2$).
To address this, Liu et al. introduced Sparsity-Constrained Optimal Transport. Instead of relying on a smooth proxy penalty, they integrated explicit, non-convex cardinality constraints directly into the OT formulation:
$$\|P_i\|_0 \leq k$$
where $\|\cdot\|_0$ counts the number of non-zero entries in a row. By leveraging a squared $k$-support norm as a tight convex relaxation, the authors proved that the resulting optimization remains tractable. This framework provides a strict mathematical guarantee on the maximum number of active connections per input, bridging the gap between optimal transport theory and the rigid execution requirements of large-scale deep learning architectures.