Scaling Optimal Transport for Massive Datasets

644 concepts508 papers1 proposal

Optimal Transport (OT) provides a mathematically rigorous way to compare probability distributions by calculating the minimum "cost" required to transform one into another. While it offers a geometry-aware alternative to simple metrics like Euclidean distance, its adoption in large-scale machine learning was long hindered by a severe computational bottleneck. Standard formulations of OT, often solved via linear programming, exhibit a cubic computational complexity ($O(n^3)$) relative to the number of data points Benamou et al..

As datasets in fields like genomics and computer vision scaled to millions of samples, researchers developed a suite of techniques to break this complexity wall, moving from exact solvers to regularized, stochastic, and low-rank approximations.

The Entropic Breakthrough and Sinkhorn Iterations

The first major step toward scalability involved changing the problem itself. By adding an entropic regularization term to the OT objective, the authors of Benamou et al. transformed the problem into a series of Kullback-Leibler (KL) divergence projections. This regularized version can be solved using Sinkhorn iterations, which involve simple, iterative matrix scaling.

While Sinkhorn iterations are significantly faster than linear programming, they still face a quadratic ($O(n^2)$) scaling bottleneck in both time and memory Halmos et al.. For a dataset with a million points, storing the $n \times n$ coupling matrix alone becomes prohibitive, requiring terabytes of memory.

Stochastic Optimization and Mini-batching

To integrate OT into deep learning, researchers shifted from solving the problem on the entire dataset to using stochastic approximations. Genevay et al. re-cast the dual OT problem as an expectation maximization task. This allowed for the use of stochastic gradient descent, enabling the computation of OT distances between continuous distributions without requiring full discretization.

In practice, many deep learning frameworks like DeepJDOT Damodaran et al. and JDOT Courty et al. utilize mini-batching to handle large-scale domain adaptation. However, mini-batching is not a perfect substitute for global OT. As Nguyen et al. argue, local batch-wise alignments can lead to "misspecified mappings"—incorrect pairings where points are matched simply because they appear in the same batch, rather than because they are truly the closest matches in the global distribution. To mitigate this, the authors propose Partial Optimal Transport (POT), which filters out these erroneous pairings by only transporting a fraction of the mass in each batch.

Breaking the Quadratic Barrier

Recent research has focused on achieving linear or log-linear complexity, finally making OT feasible for "atlas-scale" data. Several distinct strategies have emerged:

  • Low-Rank Factorization: Instead of computing a full $n \times n$ coupling matrix, Low-Rank Sinkhorn Factorization (LOT) Scetbon et al. constrains the coupling to have a low nonnegative rank. This reduces the complexity to linear time relative to the number of samples.
  • Positive Features: Scetbon demonstrated that by designing cost functions based on "positive features," Sinkhorn divergences can be computed in $O(nr)$ time, where $r$ is a small number of features, bypassing the $O(n^2)$ requirement entirely.
  • Hierarchical Refinement: The HiRef algorithm Halmos et al. uses a multi-scale approach to achieve bijective mappings in log-linear time and linear space, successfully scaling to datasets exceeding one million points.
  • Symmetry Exploitation: When data exhibits specific structures, such as cyclic symmetry, the authors of Takeda et al. show that large OT problems can be decomposed into much smaller sub-problems, yielding up to 100x speedups.

Neural Mappings and Simulation-Free OT

A final frontier in scalability involves replacing the discrete coupling matrix with a continuous neural network. The SPOT framework Xie treats the transport plan as a "push-forward" mapping, using a minimax optimization similar to a Generative Adversarial Network (GAN) to learn the transformation directly.

Similarly, in the context of temporal data and Schrödinger bridges, Zhang et al. propose "simulation-free" training. By leveraging analytically tractable reference dynamics, they avoid the need for expensive Sinkhorn iterations or complex simulations during training, providing a faster path to reconstructing trajectories in high-dimensional biological systems.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 517 papers
  2. Version 1 · 2026-10-04 · 490 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_optimal_transport_scalability_computatio_6363fac1,
  title = {optimal transport scalability (computational complexity of optimal transport)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-transport-scalability-computational-complexity-of-optimal-transport/rdr_6363fac1dfb34d16a302c6e6c4f4f9a8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_optimal_transport_scalability_computatio_6363fac1_v2,
  title = {optimal transport scalability (computational complexity of optimal transport)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-transport-scalability-computational-complexity-of-optimal-transport/rdr_6363fac1dfb34d16a302c6e6c4f4f9a8/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake