Optimal Transport (OT), often conceptualized as the "Earth Mover’s Distance," provides a mathematically rigorous framework for measuring the similarity between probability distributions, such as images or point clouds. It calculates the minimum cost required to "transport" mass from a supply distribution to a demand distribution.
While theoretically elegant, exact OT solvers are computationally prohibitive for modern, large-scale machine learning datasets. To scale up, researchers typically rely on approximations. The most popular method, the Sinkhorn algorithm, utilizes entropic regularization to accelerate computation. However, Sinkhorn suffers from a significant "precision problem": as the desired error margin ($\delta$) decreases, the algorithm becomes numerically unstable and drastically slower.
This paper introduces a deterministic, graph-theoretic algorithm to solve the OT problem with an additive error $\delta$. By adapting the classic Gabow-Tarjan scaling algorithm and providing a novel "diameter-sensitive" analysis, the authors achieve a highly competitive time complexity that is numerically stable, particularly when high precision (small $\delta$) is required.
A Return to Combinatorial Roots
Moving away from the "soft" optimization of Sinkhorn, the authors return to the "hard" combinatorial roots of graph theory. Their approach adapts the Gabow-Tarjan algorithm, originally designed for the assignment problem, to the continuous domain of optimal transport.
Key technical steps include:
- Integer Scaling: Continuous demands and supplies are transformed into integers by scaling them by a factor proportional to $1/\delta$.
- Single-Scale Primal-Dual Approach: Instead of complex multi-scale cost-scaling, the algorithm uses a single scale, maintaining "dual weights" for each node to ensure "1-feasibility."
- Two-Step Iterations: Each iteration consists of a Dijkstra-type "Hungarian Search" to adjust dual weights and find "zero-slack" edges (the currently cheapest routes), followed by a partial Depth-First Search (DFS) to find "augmenting paths" that actually move supply to demand.
- Diameter-Sensitive Analysis: The core theoretical contribution is a novel method to bound the total length of all augmenting paths. This yields a time complexity bound of $\mathcal{O}(n^2C/\delta + n(C/\delta)^2)$, notably avoiding the logarithmic factors present in many state-of-the-art approximation algorithms.
Empirical Performance and Key Insights
The algorithm was evaluated using the MNIST Handwritten Digits dataset, treating pixel intensities of $28 \times 28$ images as supply/demand and defining the transport cost as the squared Euclidean distance between pixel coordinates.
By treating OT as a graph problem rather than a regularized optimization problem, the proposed method completely avoids the numerical instability (overflow/underflow) that plagues Sinkhorn at small regularization parameters.
Key Results: * High Precision Stability: While Sinkhorn is exceptionally fast for coarse approximations, its iteration count explodes as $\delta$ decreases. The proposed combinatorial algorithm remains stable and finishes significantly faster than Sinkhorn, Greenkhorn, or APDAGD for very small values of $\delta$ (e.g., $\delta = 0.0001$). * Empirical Efficiency: In practice, the total length of augmenting paths was much smaller than the theoretical worst-case bound. The time spent actively moving mass (augmentations) accounted for less than 2% of the total execution time. * Simplicity: Relying only on standard graph traversals (Dijkstra and DFS), the algorithm is straightforward to implement and reason about compared to complex accelerated gradient methods.
Limitations and Future Directions
The primary limitation of this approach is its sequential nature. Because the algorithm relies heavily on Dijkstra’s search, it is inherently sequential and harder to parallelize on GPUs compared to Sinkhorn, which consists mostly of highly parallelizable matrix-vector multiplications.
However, the authors suggest promising avenues for future work. For geometric costs (like Euclidean distance), the "Hungarian Search" step could potentially be accelerated using Approximate Nearest Neighbor (ANN) or Dynamic Weighted Nearest Neighbor data structures. Furthermore, exploring parallel versions of this combinatorial approach could allow it to compete with Sinkhorn on modern hardware accelerators, combining theoretical stability with practical scalability.
Summary updated