Optimal Transport (OT) has emerged as a mathematically elegant framework for distribution alignment, cross-modal matching, and generative modeling. Unlike standard point-wise metrics—such as $L_2$ loss or cosine similarity—that compare representations in isolation, OT considers the geometry of the entire data space. It computes a global "transport plan" that maps one probability distribution to another with minimal cost.
However, this geometric expressiveness comes at a steep price. Standard loss functions are computationally trivial: a single forward pass yields a closed-form error metric. In contrast, evaluating an OT-based objective requires solving an explicit optimization problem inside the neural network's training or inference loop. This architectural coupling introduces a severe computational bottleneck, shifting the primary cost of deep learning from highly parallelized matrix multiplications to sequential, iterative optimization.
The Root Cause: Inner Optimization Loops
To understand why OT incurs such significant overhead, we must look at how its distances are calculated. The classic Kantorovich formulation of OT is a linear program whose computational complexity scales cubically with the number of data points ($O(N^3)$). To make this viable for deep learning, researchers widely adopt entropy-regularized OT, which can be solved via the Sinkhorn-Knopp algorithm.
While Sinkhorn iterations turn a combinatorial problem into a sequence of matrix-vector multiplications, they remain fundamentally iterative. As demonstrated by Jia Wan et al. in A Generalized Loss Function for Crowd Counting and Localization, calculating the transport plan for each batch requires running these iterative updates to convergence. Sinkhorn requires repeatedly projecting a kernel matrix onto row and column sum constraints. If a model calculates this for every mini-batch during training—as seen in the long-tailed classification framework by Jintong Gao et al. in Distribution Alignment Optimization through Neural Collapse for Long-tailed Classification—the cumulative overhead of these iterative updates slows down the gradient descent cycle compared to standard cross-entropy losses.
Granularities of the Bottleneck
The computational penalty of OT manifests at three distinct levels within modern deep learning pipelines:
1. Per-Mini-Batch Loss Functions
When used as a training objective, OT requires computing a transport plan between empirical distributions at every iteration. For instance, in missing data imputation, Boris Muzellec et al. utilize Sinkhorn divergences between random batches in Missing Data Imputation using Optimal Transport. This necessitates extensive batch sampling and repeated optimization to ensure distributional alignment, significantly increasing resource intensity relative to traditional linear or heuristic imputations. Similarly, in dense retrieval, Jingtao Zhan et al. show in Learning Discrete Representations via Constrained Clustering for Effective and Efficient Dense Retrieval (Extended Abstract) that solving Sinkhorn-Knopp assignments for every mini-batch makes the architecture highly resource-intensive to train.
2. In-Network Layers and Routing Mechanisms
Beyond loss functions, some architectures embed OT directly into their forward pass to handle feature alignment or routing. In AAformer: Auto-Aligned Transformer for Person Re-Identification, Kuan Zhu et al. introduce an online clustering mechanism based on OT within every layer of a transformer architecture. While this dynamically aligns body parts, the cumulative overhead of iterative assignment algorithms directly impacts inference speed, posing challenges for real-time applications.
A similar bottleneck occurs in few-shot segmentation; Rui Sun demonstrates in Rethinking the Correlation in Few-Shot Segmentation: A Buoys View that integrating iterative Sinkhorn algorithms into pixel-level matching layers forces a strict trade-off, requiring researchers to artificially restrict the number of optimization iterations to maintain viable inference latency.
3. Nested and Bi-Level Optimization Loops
The most severe overhead occurs when OT is embedded within nested optimization frameworks. In generative modeling, Alexander Korotin points out in Wasserstein-2 Generative Networks that estimating dual potentials often requires expensive inner optimization loops during each training iteration, creating a substantial computational burden.
This sequential dependency is also highly pronounced in trajectory inference. As explained by Amartya Banerjee et al. in Efficient Trajectory Inference in Wasserstein Space Using Consecutive Averaging, iterative refinement schemes that solve multiple OT problems sequentially create a severe bottleneck that limits reconstruction speed when high precision is required.
The Algorithmic Trade-Off: Complexity vs. Efficiency
Given these substantial computational liabilities, why do researchers continue to integrate OT into deep learning models? The answer lies in a fundamental trade-off between algorithmic complexity and data or structural efficiency.
Standard Metrics (e.g., L2, Cosine)
[Forward Pass] ──> [Closed-Form Loss] ──> [Backward Pass] (Fast but lacks global geometry)
Optimal Transport Metrics
[Forward Pass] ──> [Iterative Solver (Sinkhorn Loop)] ──> [Converged Plan] ──> [Backward Pass] (Slow but structurally efficient)
OT provides a global semantic awareness that local metrics cannot replicate. For example, in sequence-to-sequence learning, Liqun Chen et al. demonstrate in Improving Sequence-to-Sequence Learning via Optimal Transport that despite the non-trivial overhead added to the training cycle, an OT-based objective captures global semantic structures and alleviates exposure bias far better than standard word-level cross-entropy.
In vision-language pre-training, Jiali Duan et al. show in Multi-modal Alignment using Representation Codebook that using OT to map features to learnable prototypes allows models to achieve state-of-the-art zero-shot retrieval using significantly less data than massive models like CLIP. The computational cost per training step is thus offset by a dramatic increase in data efficiency.
Mitigating the Overhead
To bridge the gap between geometric accuracy and computational feasibility, researchers focus on structural approximations of the transport problem.
One prominent direction is Sliced Optimal Transport, which projects high-dimensional distributions onto one-dimensional lines where the OT problem can be solved instantly via sorting. However, extending this to complex scenarios introduces its own iterative challenges. Clément Bonet et al. explore this in Unbalanced Optimal Transport meets Sliced-Wasserstein and Slicing Unbalanced Optimal Transport, noting that while unbalanced sliced transport solvers are significantly faster than full unbalanced solvers, the requirement for multiple iterations of sorting and projection still introduces non-trivial computational overhead compared to standard sliced methods.
Another approach involves factorization through low-dimensional bottlenecks. In Making transport more robust and interpretable by moving data through a small number of anchor points, Chi-Heng Lin et al. propose routing data through a small set of learned anchor points. While this factorized transport plan offers statistical robustness and interpretability, the authors note it still faces increased computational costs due to the alternating optimization strategies (such as block-coordinate descent) required for convergence.