Scaling Optimal Transport to Millions of Samples

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2490 papers510 conceptsfrozen 2026-10-04

Optimal Transport (OT) is often described as the most "natural" way to compare two distributions. If you imagine two piles of sand, OT calculates the minimum effort required to move one pile into the shape of the other. Unlike simple pixel-wise or point-wise comparisons, OT is geometrically aware—it cares about where the mass is moving, not just whether two points overlap.

This geometric sensitivity makes OT a powerhouse for domain adaptation, as shown by Nicolas Courty and Rémi Flamary in Optimal Transport for Domain Adaptation, and for generative modeling, as explored in the course notes by Gabriel Peyré in Optimal Transport for Machine Learners.

However, OT has historically been haunted by a "computational wall." To find the optimal way to move $N$ points to $M$ locations, you typically need to compute a coupling matrix of size $N \times M$. When $N$ and $M$ reach a million—a common scale in modern genomics or high-resolution imaging—this matrix requires a trillion entries, far exceeding the memory of any modern GPU.

The Quadratic Bottleneck

The gold standard for modern OT is the Sinkhorn algorithm, which uses entropic regularization to turn the transport problem into a series of fast matrix-vector multiplications. While Sinkhorn is much faster than traditional linear programming, it still scales quadratically ($O(n^2)$) in both time and memory.

As noted by Peter Halmos and Benjamin Raphael in Hierarchical Refinement: Optimal Transport to Infinity and Beyond, this quadratic scaling prevents the application of high-resolution alignment to "atlas-scale" biological datasets. Whether it's aligning single-cell RNA sequences or 3D spatial transcriptomics slices in ST-GEARS, the sheer volume of data points makes standard Sinkhorn iterations impractical.

Strategy 1: Stochastic Optimization and Minibatches

The first major breakthrough in scaling OT was to stop looking at the whole dataset at once. In Stochastic Optimization for Large-scale Optimal Transport, Aude Genevay, marco cuturi, and Francis Bach re-cast the dual OT problem as an expectation maximization. This allows researchers to use stochastic gradient descent (SGD) to estimate transport distances by sampling small minibatches of data.

This approach is now a staple in deep learning. For instance, DeepJDOT uses minibatch OT to align latent features and labels across different domains. Similarly, Multisample Flow Matching by Aram-Alexandre Pooladian and Ricky T. Q. Chen uses minibatch couplings to "straighten" the trajectories of generative models, making them faster to train and sample.

Strategy 2: Low-Rank and Matrix Approximations

If the problem is the size of the $N \times N$ kernel matrix, why not approximate the matrix? Jason Altschuler and Alessandro Rudi demonstrated in Massively scalable Sinkhorn distances via the Nyström method that one can use the Nyström method to create a low-rank approximation of the Sinkhorn kernel. This reduces the complexity from quadratic to near-linear, enabling OT calculations on millions of points by only looking at a small, representative subset of the kernel's rows.

Strategy 3: Hierarchical and Multiscale Refinement

Another intuition for scaling is "divide and conquer." Instead of matching every point to every other point, we can match clusters of points first, then refine the matches within those clusters.

Lu Wang and Jindong Wang applied this in Cross-domain activity recognition via substructural optimal transport, finding that aligning "substructures" (clusters) is 5x faster than traditional OT while being more robust to noise. More recently, the HiRef algorithm introduced by Peter Halmos achieves bijective mappings in log-linear time by progressively refining the transport plan across a hierarchy, effectively bypassing the $O(n^2)$ memory requirement entirely.

Strategy 4: Decoupling Matching from Gradients

In generative modeling, the cost of OT is often compounded because we must solve the transport problem inside a training loop. Jose Lezama and Qiang Qiu proposed a clever workaround in Run-Sort-ReRun. By decoupling the sample-matching process (which uses sorting) from the gradient computation, they allow models to train with massive effective batch sizes—tens of thousands of samples—without exploding GPU memory. This "Run-Sort-ReRun" strategy ensures that the most expensive part of the OT calculation doesn't need to store the massive activation graphs required for backpropagation.

Why It Matters

Scaling OT isn't just about speed; it's about enabling new kinds of science. In single-cell biology, methods like Cell-MNN are moving away from quadratic OT to more scalable ODE-based representations to handle millions of cells. In robotics, PEARL uses relational trajectory alignment to transfer human preferences across tasks. As these computational bottlenecks fall, the geometric "common sense" of Optimal Transport is becoming accessible to the largest datasets in machine learning.

Papers in this version

Showing 60 of 490 papers.

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 1, frozen text):

@misc{lacuna_scaling_optimal_transport_to_millions_of_6363fac1_v1,
  title = {Scaling Optimal Transport to Millions of Samples},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-optimal-transport-to-millions-of-samples/rdr_6363fac1dfb34d16a302c6e6c4f4f9a8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}