Scaling Optimal Transport via Stochastic Dual Optimization

25 concepts19 papers1 proposal

Optimal Transport (OT) provides a geometrically rigorous framework for comparing probability distributions by computing the minimal cost required to transform one distribution into another. Despite its theoretical elegance, classical optimal transport has historically suffered from a severe computational bottleneck. Finding the exact optimal transport plan—known as the Kantorovich relaxation—requires solving a constrained linear program over an $N \times N$ coupling matrix, where $N$ is the number of data points. This primal formulation incurs a cubic computational complexity $O(N^3)$, rendering it intractable for modern, large-scale machine learning applications.

Even with the advent of entropic regularization, which smooths the objective and allows for faster optimization via the Sinkhorn algorithm, computations still scale quadratically $O(N^2)$ and require full-batch processing. As noted by Jingyi Zhang et al. in their review of modern computational OT methods, scaling optimal transport to millions of observations requires a fundamental shift away from exact, full-dataset solvers.

To overcome this limitation, a powerful paradigm has emerged: reformulating the optimal transport problem into its dual form and optimizing it using stochastic gradient methods. This approach decouples the computational complexity from the total dataset size, enabling optimal transport to scale to massive, high-dimensional datasets.

The Core Shift: From Primal Plans to Dual Expectations

The key to scaling optimal transport lies in transitioning from the primal formulation to the Kantorovich dual formulation. Instead of optimizing over a massive, constrained coupling matrix that links every source point to every target point, the dual formulation optimizes over continuous potential functions (often called Kantorovich potentials).

Crucially, as demonstrated by Aude Genevay et al. in Stochastic Optimization for Large-scale Optimal Transport, the dual formulation allows the objective function to be reframed as an expectation over the data distributions:

$$\max_{\psi, \phi} \mathbb{E}_{x \sim \mu}[\psi(x)] + \mathbb{E}_{y \sim \nu}[\phi(y)]$$

subject to the constraint that $\psi(x) + \phi(y) \leq c(x,y)$, where $c(x,y)$ is the transport cost.

When an optimization problem is structured as an expectation over random variables, it no longer requires full-batch processing. Instead of looking at the entire dataset simultaneously to compute a global transport plan, researchers can draw random mini-batches of samples to compute unbiased estimates of the gradients. This enables the use of standard stochastic optimization techniques, such as Stochastic Gradient Descent (SGD) or Stochastic Averaged Gradient (SAG).

By leveraging this dual formulation, Marin Ballu et al. show in Stochastic Optimization for Regularized Wasserstein Estimators that gradient updates can be executed with constant-time complexity per step, completely independent of the total sample size. Similarly, Marco Pegoraro et al. utilize this dual formulation in Vector Quantile Regression on Manifolds to transition from rigid linear programming to flexible, gradient-based optimization. This shift allows complex geometric statistical models to converge on large datasets in minutes rather than hours.

Minibatch Approximations and Local Couplings

An alternative, highly practical way to exploit stochasticity is to approximate global optimal transport by solving small-scale transport problems over minibatches.

Vivien Seguy et al. demonstrate in Large Scale Optimal Transport and Mapping Estimation that combining stochastic dual optimization with deep neural networks makes it possible to learn continuous transport mappings. By parameterizing the dual potentials as neural networks and updating them via mini-batch gradient descent, the computational complexity drops from quadratic relative to the entire dataset to quadratic relative only to the mini-batch size.

[Full Dataset (Millions of Points)]
               │
               ▼ (Stochastic Sampling)
    ┌─────────────────────┐
    │ Mini-batch Samples  │ ──► Compute local couplings or dual potentials
    └─────────────────────┘     (Complexity scales with batch size, not dataset size)
               │
               ▼
    ┌─────────────────────┐
    │  Gradient Update    │ ──► Backpropagate to update neural network weights
    └─────────────────────┘

This minibatch strategy is particularly effective when embedding optimal transport losses directly into deep learning architectures. For instance, in unsupervised domain adaptation, Bharath Bhushan Damodaran et al. introduce an alternating optimization strategy in DeepJDOT. The framework solves small-scale optimal transport problems on minibatches to find local couplings in a latent feature space, and then uses these couplings to update network weights via standard backpropagation.

Why do these small, localized batch approximations work so well without losing global structure? As explored by Gavin Kerrigan et al. in Dynamic Conditional Optimal Transport through Simulation-Free Flows, computing transport plans over small subsets during training drastically mitigates memory overhead while empirically maintaining the integrity of the global transport paths. Their empirical results indicate that even very small batch sizes can achieve low error rates in approximating global transport distances. This same principle underpins the work of Kristjan Greenewald et al. in $k$-Mixup Regularization for Deep Learning via Optimal Transport, where optimal transport matching on small batches provides a computationally efficient way to regularize models by capturing local data geometry.

Advanced Stochastic Solvers and Regularization

As stochastic optimal transport has matured, researchers have introduced specialized optimization schemes to handle non-smooth objectives, cross-space mappings, and noisy real-world data.

When dealing with non-smooth transport objectives, standard stochastic gradients can become unstable. To address this, Arman Rahbar et al. propose a stochastic proximal-projection algorithm in Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework. Their method incorporates memory vectors to maintain stable estimates of the gradient and proximal operators, achieving a convergence rate of $O(1/\sqrt{T})$ without ever requiring full-batch computations over the quadratic number of transport variables.

Stochastic dual methods have also unlocked solutions to cross-space transport problems, where data distributions lie in entirely different feature spaces (such as matching text corpora to image embeddings). Othmane Sebbouh et al. show in Structured Transforms Across Spaces with Cost-Regularized Optimal Transport that converting these complex, quadratic optimization problems into a cost-regularized dual formulation enables the use of stochastic gradient descent, making cross-space alignment scalable for massive datasets.

Furthermore, standard optimal transport is highly sensitive to outliers because it strictly enforces that all mass must be transported. To make the framework robust, Rama Chellappa et al. introduce a continuous stochastic relaxation of the transport objective in Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation. This relaxation allows mini-batch gradient descent to ignore noisy outliers automatically during end-to-end training. For settings where datasets have entirely different total masses, Clément Bonet et al. combine linear approximations with slicing techniques in Slicing Unbalanced Optimal Transport, achieving up to a 40x speedup over traditional solvers when computing barycenters for large scientific datasets.

Alternative Scaling Paradigms: Slicing and Decoupling

Beyond pure dual SGD, several recent architectures scale optimal transport by altering how gradients and samples interact during training.

One prominent strategy is to decouple the matching process from gradient computation entirely. In Run-Sort-ReRun: Escaping Batch Size Limitations in Sliced Wasserstein Generative Models, Jose Lezama et al. demonstrate that separating the calculation of optimal transport correspondences from the backpropagation step allows generative models to utilize massive batch sizes (tens of thousands of samples) without exploding GPU memory. This prevents mode collapse by allowing the model to capture complex distribution nuances in a single update step.

┌─────────────────────────────────────────────────────────────────────────┐
│                          Run-Sort-ReRun Loop                            │
├─────────────────────────────────────────────────────────────────────────┤
│  1. Run: Forward pass to generate features (No gradient tracking)       │
│  2. Sort: Find optimal transport correspondences on massive batch       │
│  3. ReRun: Forward pass on matched pairs with gradient tracking active  │
└─────────────────────────────────────────────────────────────────────────┘

In the domain of generative flow models, explicit optimal transport solvers can sometimes be bypassed altogether. Álvaro Cartea et al. introduce Weighted Conditional Flow Matching, which uses a soft-weighting scheme for training pairs based on a Gibbs kernel. This approach implicitly approximates entropic optimal transport paths, scaling more effectively with large batch sizes than traditional minibatch solvers and yielding straighter, faster sampling trajectories.

Finally, stochastic updates can be paired with metric learning to discover the underlying relationships between features. Geert-Jan Huizing et al. demonstrate in Unsupervised Ground Metric Learning Using Wasserstein Singular Vectors that combining entropic regularization with stochastic mini-batch updates allows a system to approximate transport plans via the Sinkhorn algorithm while performing partial updates to a distance matrix. This enables the unsupervised learning of ground metrics on high-dimensional datasets where exact optimal transport would be computationally prohibitive.

Key Foundational Work

Stochastic Optimization for Large-scale Optimal Transport (2016) — contributed 3 concept elements to this direction.
Large Scale Optimal Transport and Mapping Estimation (2018) — contributed 2 concept elements to this direction.
DeepJDOT: Deep Joint Distribution Optimal Transport for Unsupervised Domain Adaptation (2018) — contributed 1 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_stochastic_optimal_transport_b7cb8215,
  title = {stochastic optimal transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-optimal-transport/rdr_b7cb821561ce4799a11c995c9c8d7454},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

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

These directions overlap with this one through shared papers.

See something wrong? Report a mistake