On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms

Abstract

We provide theoretical analyses for two algorithms that solve the regularized optimal transport (OT) problem between two discrete probability measures with at most $n$ atoms. We show that a greedy variant of the classical Sinkhorn algorithm, known as the