Differentiable Optimal Transport with Entropic Regularization

77 concepts63 papers1 proposal

In machine learning, we frequently need to compare distributions or find correspondences between sets of items. Whether we are matching predicted bounding boxes to ground-truth objects in a vision model, aligning words across translation pairs, or measuring the distance between a model's generated output and the true data distribution, we face a fundamental challenge: how do we compute a globally optimal alignment in a way that allows gradients to flow?

The mathematical gold standard for this task is Optimal Transport (OT), often evaluated via the Earth Mover's Distance (EMD). Optimal transport finds the minimal cost required to transform one probability distribution into another given a specific transport cost matrix. Unfortunately, solving the classic optimal transport problem requires solving a discrete linear program. Algorithms like the Hungarian method or network simplex are combinatorial; they operate on discrete steps.

For deep learning, this creates a fatal bottleneck. Combinatorial optimization algorithms are non-differentiable step functions—their outputs change discretely, meaning their derivatives are zero almost everywhere and undefined at decision boundaries. You cannot backpropagate a loss through a discrete solver. Furthermore, these algorithms scale poorly (often $O(N^3)$), making them too slow to sit inside a neural network's training loop.

Differentiable optimal transport solves this by adding a simple mathematical twist: entropic regularization. By penalizing the sharpness of the transport plan, we transform a rigid, discrete combinatorial problem into a smooth, strictly convex optimization landscape that can be solved using fast, fully differentiable matrix operations.


The Mechanism: Smoothing the Landscape with Entropy

To understand why entropic regularization works, let us look at the standard optimal transport formulation. Given two discrete distributions, we want to find a transport plan matrix $P$ that minimizes the total cost $\langle P, C \rangle$, where $C$ is the pairwise cost matrix between elements, subject to marginal constraints ensuring all mass is correctly distributed.

Entropic optimal transport modifies this objective by subtracting an entropy term, $H(P) = -\sum_{i,j} P_{i,j} \log P_{i,j}$:

$$\min_{P} \langle P, C \rangle - \epsilon H(P)$$

Here, $\epsilon > 0$ is a regularization parameter. This addition completely changes the geometry of the problem:

  1. Strict Convexity: The objective function becomes strictly convex, guaranteeing a unique global solution.
  2. Soft Assignments: Instead of producing a sparse, "hard" permutation matrix (where entries are strictly 0 or 1), the optimal transport plan $P$ becomes a "soft," dense matrix where every element is strictly positive.

According to Sinkhorn’s theorem, the solution to this regularized problem has a specific scaling form:

$$P = \text{diag}(u) \, K \, \text{diag}(v)$$

where $K = \exp(-C / \epsilon)$ is an element-wise kernel matrix derived from our costs, and $u$ and $v$ are scaling vectors. We can find $u$ and $v$ using the Sinkhorn-Knopp algorithm, which simply alternates between two scaling updates:

$$u \leftarrow \frac{1}{K v}, \quad v \leftarrow \frac{1}{K^T u}$$

This iterative scaling process requires only basic matrix-vector multiplications and element-wise divisions. Because every single operation in a Sinkhorn iteration is continuous and differentiable, the entire solver can be unrolled as a sequence of layers within a neural network. Gradients can flow directly through the unrolled iterations of the solver back to the cost matrix $C$, and ultimately to the neural network features that generated $C$.


Why It Works: Building Intuition on Gradient Flow

To see why this enables end-to-end training, consider what happens to the gradients as we adjust the regularization parameter $\epsilon$.

If $\epsilon$ is close to zero, the regularized problem behaves like standard, unregularized optimal transport. The transport plan $P$ approaches a hard, discrete assignment. If a node shifts slightly in feature space, the optimal matching matrix does not change at all—until it hits a threshold and suddenly snaps to a different discrete matching. The derivative of the output with respect to the input features is zero almost everywhere, providing no useful signal for gradient descent.

Hard Matching (ε → 0):   [Input Features] ──> [Discrete Snap] ──> [Zero Gradients]
Soft Matching (ε > 0):   [Input Features] ──> [Continuous Plan] ──> [Smooth Gradients Flow]

When we increase $\epsilon$, we inject smoothness. Every element in the source distribution transports at least a tiny fraction of its mass to every element in the target distribution. If we change a feature vector slightly, the cost matrix $C$ changes, which immediately and continuously alters the entire soft transport plan $P$. Because the relationship between the features, the costs, and the final transport plan is smooth and continuous, the gradients are non-zero and well-behaved.

As demonstrated by Johannes Gasteiger et al. in Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More, we can also leverage Danskin's theorem or implicit differentiation to compute exact gradients at the convergence of the Sinkhorn algorithm. This allows us to bypass storing the intermediate states of the unrolled loop altogether, saving substantial memory during backpropagation.


Applications Across the Deep Learning Landscape

By turning optimal transport into a plug-and-play differentiable layer, researchers have unlocked new capabilities across a wide variety of domains.

1. Differentiable Matching and Assignment Layers

In tasks that require finding explicit correspondences between two sets of features, differentiable optimal transport acts as a soft matching oracle.

For example, in object detection, the traditional Detection Transformer (DETR) relies on the rigid, non-differentiable Hungarian algorithm to match predicted bounding boxes to ground-truth objects. Masoumeh Zareapoor et al. address this in Fractional Correspondence Framework in Detection Transformer by reframing assignment as an entropy-regularized optimal transport task. By utilizing the Sinkhorn algorithm, they make the matching step fully differentiable and parallelizable on hardware accelerators, significantly accelerating training convergence.

A similar approach is taken by the authors of Normalized Matching Transformer to handle sparse keypoint matching, allowing the entire pipeline—from raw feature extraction to final geometric correspondence—to be optimized end-to-end via gradient descent. In heterogeneous data fusion, Zhiwei Tang et al. deploy entropic optimal transport within Low-Rank Matrix Recovery with Unknown Correspondence to solve complex combinatorial row-alignment problems jointly with parameter estimation.

2. Distribution Alignment Losses

Instead of penalizing point-wise errors, models can use differentiable optimal transport to minimize the geometric distance between entire distributions.

In human pose estimation, models traditionally try to predict a blurry Gaussian heatmap around a joint. Haoxuan Qu et al. show in Heatmap Distribution Matching for Human Pose Estimation that reframing this as a distribution matching problem using a Sinkhorn-approximated EMD loss allows models to learn directly from exact point annotations, pulling the predicted heatmap mass precisely toward the true coordinates.

Point-wise Loss (MSE):   Compares pixel-by-pixel. Missing by 5 pixels costs the same as missing by 50 pixels if the distributions don't overlap.
Optimal Transport Loss:  Measures geometric distance. Moving mass further costs more, providing a smooth monotonic gradient.

This geometric awareness is also highly effective in auto-regressive language modeling. Siyu Ren et al. introduce EMO: EARTH MOVER DISTANCE OPTIMIZATION FOR AUTO-REGRESSIVE LANGUAGE MODELING, which replaces standard cross-entropy with a differentiable upper bound of the EMD. This forces the language model to minimize semantic distances in vocabulary space rather than treating all incorrect token predictions as equally wrong.

3. Representation Learning and Deep Clustering

Reframing classical unsupervised algorithms through regularized optimal transport allows models to learn structured latent spaces end-to-end.

Gabriel Dulac-Arnold et al. demonstrate this in Differentiable Deep Clustering with Cluster Size Constraints by casting the $k$-means clustering problem as an optimal transport problem. By applying entropic regularization via Sinkhorn's algorithm, they optimize data representations and cluster assignments simultaneously while enforcing global constraints on cluster sizes.

Similarly, Charlie Frogner et al. utilize Sinkhorn divergences in Learning Embeddings into Entropic Wasserstein Spaces to embed complex data structures (like graphs and hierarchies) directly as probability distributions rather than single points, capturing intricate geometric relationships with minimal distortion.


Overcoming Practical Challenges: Stability and Scale

While entropic regularization makes optimal transport differentiable, deploying it in deep learning requires addressing two key practical hurdles: numerical stability and computational scaling.

Numerical Stability in the Log-Domain

When the regularization parameter $\epsilon$ is chosen to be very small to achieve a sharper, more precise matching, the kernel matrix $K = \exp(-C / \epsilon)$ can suffer from severe numerical underflow or overflow. To prevent gradients from vanishing or exploding during backpropagation, implementations often perform the Sinkhorn scaling steps entirely within the log-domain. As seen in works like Towards Domain-Generalizable Paraphrase Identification by Avoiding the Shortcut Learning, executing updates using stable operators like logsumexp ensures robust gradient propagation even under tight regularization constraints.

Scaling to High Dimensions

Although the Sinkhorn algorithm reduces the computational complexity of optimal transport from cubic to quadratic ($O(N^2)$), a quadratic cost is still prohibitively expensive when dealing with large graphs, long sequences, or high-dimensional embeddings.

To break this bottleneck, Johannes Gasteiger et al. introduce LCN-Sinkhorn in Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More. By combining sparse approximations via Locality Sensitive Hashing (LSH) with low-rank approximations via the Nyström method, they achieve a log-linear time complexity. Crucially, because their hybrid approximation remains compatible with Danskin's theorem, the scalable transport distance retains its full differentiability, allowing deep neural networks to optimize global structural properties at scale.

Key Foundational Work

Supervised Word Mover's Distance (2016) — contributed 2 concept elements to this direction.
Optimal Transport for Deep Joint Transfer Learning (2017) — contributed 1 concept elements to this direction.
On Wasserstein Reinforcement Learning and the Fokker-Planck equation (2017) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_differentiable_optimal_transport_4222335b,
  title = {differentiable optimal transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/differentiable-optimal-transport/rdr_4222335ba814400bb66454978d8a3337},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_differentiable_optimal_transport_4222335b_v1,
  title = {differentiable optimal transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/differentiable-optimal-transport/rdr_4222335ba814400bb66454978d8a3337/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake