Abstract: Optimal transport (OT) distances are finding evermore applications in machine learning and computer vision, but their wide spread use in larger-scale problems is impeded by their high computational cost. This paper introduces a new family of randomized algorithms for solving entropy-regularized OT problems, generalizing the state-of-the-art greedy "Greenkhorn" algorithm and proving that these stochastic methods achieve optimal convergence rates while often performing better in practice.
Introduction
Optimal Transport (OT) provides a geometrically sensitive framework for comparing probability distributions, yet its classical computation cost of $O(n^3 \log n)$ remains a significant barrier for large-scale machine learning. To mitigate this, researchers often employ entropic regularization, enabling the use of the Sinkhorn algorithm. While the greedy "Greenkhorn" variant recently improved convergence by updating only the most violated constraints, a gap remained for a more flexible, randomized approach.
This paper introduces Stochastic Sinkhorn, a new family of randomized algorithms that generalize the greedy Greenkhorn approach. By sampling row or column updates based on their violation of transport constraints, these methods maintain optimal convergence rates while offering superior empirical performance.
The Stochastic Sinkhorn Framework
The core innovation lies in Algorithm 2, which replaces the deterministic selection of Sinkhorn or the purely greedy selection of Greenkhorn with a stochastic sampling process. Each row and column index is assigned a probability proportional to its constraint violation.
The authors define a family of increasing probability functions $\Psi$. For instance, using a Softmax function with temperature $T$, the algorithm can transition from uniform sampling (high $T$) to purely greedy selection (low $T$). Crucially, the authors developed an $O(n)$ update rule for marginal violations, ensuring that each stochastic step is as computationally efficient as a single greedy update. Theoretically, any algorithm in this family achieves an iteration complexity of $O(n/\epsilon^2)$, matching the best-known bounds for Greenkhorn.
Experimental Evaluation
The algorithms were evaluated on MNIST digit images ($n=784$) and synthetic random histograms. The experiments focused on the "distance from the transport polytope" as a function of row/column updates.
As shown in Figure 1, Stochastic Sinkhorn often outperforms both the standard Sinkhorn and the greedy Greenkhorn, particularly in regimes with low penalization. In these scenarios, being "softly greedy"—allowing for randomized updates rather than always picking the absolute maximum violation—leads to faster convergence to high-accuracy solutions. Furthermore, the algorithm demonstrates high stability, with the standard deviation of the distance metric decreasing rapidly across iterations.
Discussion and Future Work
While Stochastic Sinkhorn offers clear advantages in convergence speed and theoretical flexibility, it shares a limitation with Greenkhorn: its sequential nature. Because it updates one index at a time, it is less naturally suited for GPU acceleration than the original Sinkhorn algorithm, which relies on large matrix-vector products.
Future research directions include the formal analysis of Block Stochastic Sinkhorn, which updates multiple indices simultaneously to improve parallelization. Preliminary results suggest that increasing the block size can maintain convergence efficiency while potentially unlocking hardware-level speedups. Additionally, automated methods for tuning hyperparameters like the Softmax temperature $T$ could further enhance the algorithm's robustness across diverse datasets.
Summary updated