Accelerating Optimal Transport Computations

21 concepts19 papers1 proposal

Optimal Transport (OT) provides a geometrically rigorous framework for comparing probability distributions by computing the minimal cost required to warp one distribution into another. Despite its mathematical elegance and widespread utility in machine learning, computer vision, and data analysis, standard OT suffers from a severe computational bottleneck: solving the classic Monge-Kantorovich linear program scales cubically ($O(N^3)$) with the number of data points $N$.

To unlock the potential of OT for large-scale applications, a major research direction focuses on accelerating these computations. Rather than treating OT as a generic, rigid optimization problem, modern approaches bypass the cubic bottleneck by rewriting the optimization landscape, exploiting underlying geometric structures, factoring internal matrices, or amortizing the computation entirely through machine learning.


Smoothing the Optimization Landscape

Standard OT is a linear program with a rigid, non-smooth objective function. Its solution space features sharp corners, forcing traditional solvers to iteratively crawl along the boundaries of a high-dimensional polytope. By adding a regularization term, we can "round out" these corners, transforming a non-smooth problem into a strictly convex, smooth optimization landscape that is far friendlier to rapid, derivative-based algorithms.

The most common form of this strategy is entropic regularization, which enables the use of the fast, iterative Sinkhorn-Knopp algorithm. To accelerate this further, Alexis Thibault et al. introduced an "overrelaxation" technique to the standard Bregman projection steps in Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport. By extrapolating successive projection steps—akin to Successive Over-Relaxation methods in linear algebra—the authors achieved an order of magnitude speedup for challenging problems with small regularization parameters while maintaining global convergence guarantees.

Other regularization terms offer distinct mathematical advantages. For instance, Wuchen Li et al. incorporated Fisher information regularization into the dynamic Benamou-Brenier formulation in Computations of Optimal Transport Distance with Fisher Information Regularization. This regularization yields a strictly convex and smooth optimization problem that converges rapidly using Newton's method, often reaching a solution within dozens of iterations rather than thousands.

[Rigid Linear Program]  ───(Add Regularization)───►  [Smooth, Convex Landscape]
  - Sharp corners                                      - Rounded boundaries
  - Slow simplex/proximal solvers                      - Fast Newton / Sinkhorn steps
  - O(N³) complexity                                   - Drastically fewer iterations

For complex variants like Unbalanced Optimal Transport (UOT)—where the total mass of the two distributions does not match—Hoang H. Nguyen et al. applied a Gradient Extrapolation Method (GEM) to a novel dual formulation in On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error, significantly improving theoretical complexity bounds relative to the regularization parameter.

These smoothing techniques yield massive practical dividends across diverse fields. In communication theory, Wenhao Ye et al. reformulated the computation of mismatched channel capacity bounds (the LM rate) as an OT problem in An Optimal Transport Approach to the Computation of the LM Rate, allowing the Sinkhorn algorithm to outperform traditional convex optimization toolboxes by over 400 times. To handle multi-distribution scenarios, Michael I. Jordan et al. extended these regularized acceleration concepts to Multimarginal Optimal Transport (MOT) in On the Complexity of Approximating Multimarginal Optimal Transport, utilizing an estimate sequence technique to improve complexity bounds for approximating MOT.


Dimensionality Reduction via Slicing and Geometric Projections

In one dimension, optimal transport is trivial. Because points on a line can be ordered monotonically, the optimal transport plan is obtained simply by sorting the datasets, reducing the computational complexity from $O(N^3)$ to a mere $O(N \log N)$. "Slicing" leverages this property by projecting high-dimensional distributions onto a collection of one-dimensional lines, solving the trivial 1D transport problems, and aggregating the results to approximate the high-dimensional distance.

While slicing is straightforward in flat Euclidean spaces, data often lives on non-linear manifolds. To compute Wasserstein distances on a hypersphere, Clément Bonet et al. developed the Spherical Sliced-Wasserstein (SSW) framework in Spherical Sliced-Wasserstein. By projecting spherical distributions onto "great circles" and utilizing closed-form 1D solutions, the authors achieved an $O(N \log N)$ complexity that respects the underlying spherical geometry. Similarly, Michael Quellmalz et al. introduced vertical slices and normalized semicircle transforms in Sliced Optimal Transport on the Sphere, reducing the computation of Wasserstein barycenters from hours to fractions of a second while preserving sharp features in the interpolated distributions.

High-Dim Distribution ───(Project onto 1D Subspaces)───► Ordered 1D Arrays ───(Sort)───► O(N log N) OT Plan

When data cannot be easily sliced but still possesses geometric structure, we can exploit the manifold's intrinsic properties. For curves on homogeneous spaces like spheres or Lie groups, Zhe Su et al. extended the Square Root Velocity (SRV) framework in The Square Root Velocity Framework for Curves in a Homogeneous Space. By lifting curves into higher-dimensional group structures, the authors derived explicit formulas that allow thousands of pairwise manifold distances to be calculated in a fraction of the time required by traditional methods.

For general high-dimensional manifolds where exact geodesic distances are prohibitively expensive, Guillaume Huguet et al. proposed Geodesic Sinkhorn in Geodesic Sinkhorn For Fast and Accurate Optimal Transport on Manifolds. Instead of computing exact geodesics, they approximated a heat-kernel-based geodesic distance using Chebyshev polynomials on sparse graph Laplacians, achieving near-linear time complexity and reducing computation times from hundreds of seconds to around ten seconds.


Exploiting Matrix Structure and Graph Factorization

The core computational bottleneck of regularized OT solvers like Sinkhorn is the repeated multiplication of a kernel cost matrix by a scaling vector, which inherently takes quadratic ($O(N^2)$) time. If we can find or enforce a specific algebraic structure within this matrix—such that it can be factored into sparser or simpler components—we can reduce this multiplication step to true linear time ($O(N)$).

In Fast Sinkhorn II: Collinear Triangular Matrix and Linear Time Accurate Computation of Optimal Transport, Qichen Liao et al. introduced Collinear Triangular Matrices (COLT). By integrating COLT optimizations into the Inexact Proximal Point method (IPOT), the authors achieved a linear $O(N)$ time complexity for accurate OT computations, bridging the gap between the accuracy of proximal methods and the speed of Sinkhorn-like algorithms.

Standard Sinkhorn:       [Kernel Matrix (N x N)]   x [Vector (N)]  ►  O(N²) Bottleneck
COLT / Factorization:    [Sparse / Triangular]     x [Vector (N)]  ►  O(N) Linear Time

For data naturally represented as point clouds or graphs, Krzysztof Marcin Choromanski et al. introduced SeparatorFactorization (SF) and RFDiffusion (RFD) in Efficient Graph Field Integrators Meet Point Clouds. By leveraging structural graph theory and random feature embeddings, they enabled sub-quadratic field integration on graphs, dramatically accelerating Gromov-Wasserstein and Fused Gromov-Wasserstein computations for datasets containing millions of points.

Furthermore, custom algorithmic structures can prevent computational waste on outliers. Shintaro Nakamura et al. developed alternate projection algorithms with mathematical truncation steps in Robust computation of optimal transport by β-potential regularization. This $\beta$-potential regularization prevents probability mass from being wasted on extreme outliers, achieving massive speedups over general-purpose convex solvers while simultaneously performing outlier detection. In 2D spatial applications, Léo Lebrat et al. designed a fast descent algorithm in Optimal Transport Approximation of 2-Dimensional Measures to approximate target measures with structured points or curves, outperforming standard convolution-based methods by 1–2 orders of magnitude.


Amortization: Learning to Transport

Traditional OT solvers treat every new pair of distributions as a completely isolated problem, starting the optimization process from scratch. However, in many real-world applications—such as generative modeling or iterative data alignment—we repeatedly solve highly similar OT problems. Amortization bypasses the optimization loop entirely by training a neural network to predict the optimal transport plan or its dual variables directly from the input distributions.

In Meta Optimal Transport, Brandon Amos et al. demonstrated that parameterizing the dual variables with a neural network allows the model to learn the underlying mapping of the transport problem. By outputting a high-quality "warm-start" initialization for standard iterative solvers, this approach achieves speedups of several orders of magnitude across complex domains like continuous color spaces and spherical manifolds.

Traditional:  [New Distributions] ──► [Run Iterative Solver From Scratch] ──► [OT Plan] (Slow)
Amortized:    [New Distributions] ──► [Trained Neural Network] ───────────► [OT Plan] (Instant)

Taking amortization a step further, Stefano Peluchetti proposed a non-iterative framework called Coupled Schrödinger Bridge Matching (BM$^2$) in BM$^2$: Coupled Schrödinger Bridge Matching. Instead of relying on iterative scaling algorithms to solve entropic optimal transport, BM$^2$ learns dynamic transport maps directly. This non-iterative method consistently outperforms traditional iterative benchmarks across various dimensions and regularization settings, proving that learning-based approaches can entirely replace optimization loops for computing transport maps.

Key Foundational Work

Computations of optimal transport distance with Fisher information regularization (2018) — contributed 1 concept elements to this direction.
The Square Root Velocity Framework for Curves in a Homogeneous Space (2017) — 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_accelerated_optimal_transport_c242229e,
  title = {accelerated optimal transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/accelerated-optimal-transport/rdr_c242229e4e9b4a809a9f1a57e8b55f09},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

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

These directions overlap with this one through shared papers.

See something wrong? Report a mistake