Abstract
This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. The resulting rate for approximating the optimal transport (OT) has been improved from $\widetilde{O}({n^{2.5}}/\epsilon)$ to $\widetilde{O}({n^2}/\epsilon)$, where $n$ is the problem size and $\epsilon$ is the accuracy level. In particular, we propose an accelerated primal-dual stochastic mirror descent algorithm with variance reduction. Such special design helps us improve the rate compared to other accelerated primal-dual algorithms. We further propose a batch version of our stochastic algorithm, which improves the computational performance through parallel computing. To compare, we prove that the computational complexity of the Stochastic Sinkhorn algorithm is $\widetilde{O}({n^2}/{\epsilon^2})$, which is slower than our accelerated primal-dual stochastic mirror algorithm. Experiments are done using synthetic and real data, and the results match our theoretical rates. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $\widetilde{O}({n^2}/\epsilon)$ for solving OT.
Introduction
Optimal Transport (OT) serves as a mathematical "gold standard" for measuring distances between probability distributions, determining the most efficient way to transform one mass configuration into another. Despite its power, standard OT is computationally intensive for large datasets, scaling poorly with the number of data points ($n$). To address this, researchers utilize Entropic Regularization, which smooths the problem and enables faster solvers like the Sinkhorn algorithm. However, first-order algorithms have historically faced a theoretical complexity wall of $\widetilde{O}(n^{2.5}/\epsilon)$. This paper introduces PDASMD, an algorithm that breaks this barrier to reach $\widetilde{O}(n^2/\epsilon)$.
Methodology
The proposed algorithm, Primal-Dual Accelerated Stochastic Proximal Mirror Descent (PDASMD), integrates three critical components:
- Dual Finite-Sum Reformulation: The entropic OT problem is transformed into a "semi-dual" form, making it perfectly suited for stochastic optimization.
- Variance Reduction (Katyusha Acceleration): By incorporating variance reduction techniques, specifically Katyusha momentum, the algorithm stabilizes stochastic noise. This "magnet" effect pulls estimates toward a stable average, preventing divergence and accelerating convergence.
- Mirror Descent: Utilizing mirror descent allows the algorithm to adapt to the specific geometry of the probability simplex. Specifically, by choosing the $\ell_\infty$ norm for their mirror descent framework, the authors achieved a better dependency on the problem size $n$ compared to standard $\ell_2$ norm approaches.
Additionally, the authors developed PDASMD-B, a batch version designed for parallel computing, which offers sublinear speedups when distributed across multiple processors.
Theoretical Advancements
The primary contribution is the improvement of the theoretical complexity. While previous accelerated primal-dual algorithms reached $\widetilde{O}(n^{2.5}/\epsilon)$, PDASMD achieves $\widetilde{O}(n^2/\epsilon)$. This quadratic scaling is significantly more efficient for large-scale applications. Furthermore, the authors provide a tighter complexity bound for the Stochastic Sinkhorn algorithm at $\widetilde{O}(n^2/\epsilon^2)$, demonstrating that PDASMD is theoretically superior when high accuracy (small $\epsilon$) is required.
Experimental Validation
The theoretical claims were validated using both synthetic and real-world datasets, including MNIST, the Two-Moons benchmark for domain adaptation, and natural images for color transfer tasks. Empirical results confirmed the $n^2$ scaling, with log-log plots of operations versus problem size showing a slope of approximately 2. In domain adaptation tasks, PDASMD outperformed Sinkhorn-based methods, particularly in challenging scenarios with large distribution rotations. Additionally, the batch version (PDASMD-B) demonstrated effective parallel speedup, reducing computation time by a factor of roughly $\sqrt{B}$ for a batch size $B$.
Conclusion
PDASMD represents a significant step forward in making Optimal Transport practical for big-data applications. While challenges remain—such as the dependency on the smoothness factor $\gamma$ and communication overhead in parallel implementations—the achievement of $\widetilde{O}(n^2/\epsilon)$ complexity sets a new benchmark for first-order OT solvers. Future work may explore hybrid approaches that combine PDASMD's theoretical speed with the empirical stability of traditional methods.
Summary updated