Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods
Gen Li, Yanxi Chen, Yu Huang, Yuejie Chi, H. Vincent Poor, Yuxin Chen · SIAM Journal on Optimization · 2025
Abstract. Efficient computation of the optimal transport distance between two distributions serves as an algorithm subroutine that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within [Formula: see text] additive accuracy with runtime [Formula: see text], where [Formula: see text] denotes the dimension of the probability distributions of interest. Our algorithm achieves the state-of-the-art computational guarantees among all first-order methods, while exhibiting favorable numerical performance compared to classical algorithms like Sinkhorn and Greenkhorn. Underlying our algorithm designs are two key elements: (a) converting the original problem into a bilinear minimax problem over probability distributions; (b) exploiting the extragradient idea—in conjunction with entropy regularization and adaptive learning rates—to accelerate convergence.