Optimal Transport (OT) and the Wasserstein distance provide a geometrically meaningful way to compare probability distributions. Unlike metrics that compare distributions pointwise (such as Kullback-Leibler divergence), the Wasserstein distance incorporates the underlying geometry of the space by calculating the minimum "work" required to alter one distribution into another.
However, computing the exact Wasserstein distance is notoriously expensive. For two discrete distributions of size $n$, finding the optimal transport plan requires solving a linear programming problem. As noted by Altschuler et al. and Yamada et al., standard exact solvers scale at a cubic rate of $O(n^3 \log n)$. This cubic bottleneck makes exact OT computationally prohibitive for modern, large-scale machine learning applications.
To bypass this limitation, researchers have developed several distinct algorithmic paradigms that trade exactness for scalability. Understanding why these approximations work requires looking at how they alter the underlying optimization problem.
Entropic Smoothing and Matrix Scaling
The most widely adopted approach to scaling optimal transport introduces an entropic regularization term to the objective function. In its original form, the OT problem searches for a sparse, discrete coupling matrix that minimizes transport costs. This sparsity makes the optimization combinatorial and rigid.
By adding an entropy penalty to the transport plan, the objective function becomes strictly convex. This smoothing forces the optimal coupling matrix to lose its strict sparsity and instead take on a specific algebraic structure: it can be written as a diagonal scaling of a kernel matrix, $P = \text{diag}(u) K \text{diag}(v)$, where $K$ is determined by the ground distances.
This structural shift allows researchers to use the Sinkhorn-Knopp algorithm, which iteratively updates the scaling vectors $u$ and $v$ using simple, highly parallelizable matrix-vector multiplications. As demonstrated by Cuturi et al., this turns a heavy linear programming problem into a sequence of GPU-friendly operations. Furthermore, Altschuler et al. provided theoretical guarantees proving that this regularization yields a near-linear time approximation of $\tilde{O}(n^2 / \epsilon^2)$. To accelerate this further in practice, Ho introduced accelerated primal-dual coordinate descent methods that optimize these scaling steps with tighter complexity bounds.
Dimensionality Reduction via Slicing
Another paradigm circumvents the high-dimensional bottleneck by exploiting a unique property of optimal transport in one dimension.
In a 1D vector space, calculating the Wasserstein distance does not require optimization at all. If you sort the samples from both distributions, the optimal transport plan is simply a monotonic matching: the $i$-th sorted point of the first distribution maps directly to the $i$-th sorted point of the second. Thus, the computational complexity drops from $O(n^3)$ to a mere $O(n \log n)$ sorting step.
The Sliced Wasserstein (SW) distance, utilized by Kolouri et al., leverages this efficiency by projecting high-dimensional distributions onto a collection of random 1D lines (or "slices"). The 1D Wasserstein distance is computed for each projection, and the results are averaged.
High-Dimensional Space 1D Projections (Sorting)
o * o---*
o * =======> o-----* (Trivial O(n log n) matching)
o * o-------*
While independent random projections are computationally cheap, they can miss crucial structural features of the high-dimensional space. To resolve this, Nguyen et al. developed Markovian Sliced Wasserstein distances. Instead of choosing projections completely at random, the authors use a first-order Markov chain to sequentially generate highly informative, dependent projections, capturing the distribution's geometry much more effectively with fewer slices.
Hierarchical Tree Approximations
A third major scalability strategy alters the ground metric itself. Instead of computing distances in an arbitrary Euclidean space, this approach embeds or approximates the data structure using a hierarchical tree graph.
When the underlying metric space is a tree, the optimal transport problem admits a closed-form solution. Because there is only one valid path between any two nodes on a tree, mass cannot be routed in multiple ways. The optimal flow can be computed in a single bottom-up pass by looking at the mass imbalance at each node and multiplying it by the length of the incoming edge.
The authors of Scalable Nearest Neighbor Search for Optimal Transport exploited this property to build Flowtree, an algorithm that decouples the flow computation from the cost matrix to enable rapid nearest-neighbor queries over massive datasets. To make this tree structure adaptive to specific tasks, Sato et al. introduced Supervised Tree-Wasserstein distances, making the tree-building process fully differentiable. By optimizing the tree structure via a contrastive loss, the authors created a framework that retains the linear-time computational speed of tree-based transport while capturing complex semantic relationships.