transportation polytope

We present several new complexity results for the entropic regularized algorithms that approximately solve the optimal transport (OT) problem between two discrete probability measures with at most n atoms. First, we improve the complexity bound of a greedy variant of Sinkhorn, known as Greenkhorn, from Õ(n²ε⁻³) to Õ(n²ε⁻²). Notably, our result can match the best known complexity bound of Sinkhorn and help clarify why Greenkhorn significantly outperforms Sinkhorn in practice in terms of row/column updates as observed by Altschuler et al. (2017). Second, we propose a new algorithm, which we refer to as APDAMD and which generalizes an adaptive primal-dual accelerated gradient descent (APDAGD) algorithm (Dvurechensky et al., 2018) with a prespecified mirror mapping ϕ. We prove that APDAMD achieves the complexity bound of Õ(n²√δε⁻¹) in which δ > 0 stands for the regularity of ϕ. In addition, we show by a counterexample that the complexity bound of Õ(min{n⁹/⁴ε⁻¹, n²ε⁻²}) proved for APDAGD before is invalid and give a refined complexity bound of Õ(n⁵/²ε⁻¹). Further, we develop a deterministic accelerated variant of Sinkhorn via appeal to estimated sequence and prove the complexity bound of Õ(n⁷/³ε⁻⁴/³). As such, we see that accelerated variant of Sinkhorn outperforms Sinkhorn and Greenkhorn in terms of 1/ε and APDAGD and accelerated alternating minimization (AAM) (Guminov et al., 2021) in terms of n. Finally, we conduct the experiments on synthetic and real data and the numerical results show the efficiency of Greenkhorn, APDAMD and accelerated Sinkhorn in practice.

We study the complexity of approximating the multimarginal optimal transport (MOT) distance, a generalization of the classical optimal transport distance, considered here between m discrete probability distributions supported each on n support points. First, we show that the standard linear programming (LP) representation of the MOT problem is not a minimum-cost flow problem when m ≥ 3. This negative result implies that some combinatorial algorithms, e.g., network simplex method, are not suitable for approximating the MOT problem, while the worst-case complexity bound for the deterministic interior-point algorithm remains a quantity of Õ(n^{3m}). We then propose two simple and deterministic algorithms for approximating the MOT problem. The first algorithm, which we refer to as multimarginal Sinkhorn algorithm, is a provably efficient multimarginal generalization of the Sinkhorn algorithm. We show that it achieves a complexity bound of Õ(m^{3}n^{m}ε^{−2}) for a tolerance ε ∈ (0, 1). This provides a first near-linear time complexity bound guarantee for approximating the MOT problem and matches the best known complexity bound for the Sinkhorn algorithm in the classical OT setting when m = 2. The second algorithm, which we refer to as accelerated multimarginal Sinkhorn algorithm, achieves the acceleration by incorporating an estimate sequence and the complexity bound is Õ(m^{3}n^{m+1/3}ε^{−4/3}). This bound is better than that of the first algorithm in terms of 1/ε, and accelerated alternating minimization algorithm (Tupitsa et al., 2020) in terms of n. Finally, we compare our new algorithms with the commercial LP solver GUROBI. Preliminary results on synthetic data and real images demonstrate the effectiveness and efficiency of our algorithms.

Optimal transport (OT) theory can be informally described using the words of the French mathematician Gaspard Monge (1746-1818): A worker with a shovel in hand has to move a large pile of sand lying on a construction site. The goal of the worker is to erect with all that sand a target pile with a prescribed shape (for example, that of a giant sand castle). Naturally, the worker wishes to minimize her total effort, quantified for instance as the total distance or time spent carrying shovelfuls of sand. Mathematicians interested in OT cast that problem as that of comparing two probability distributions, two different piles of sand of the same volume. They consider all of the many possible ways to morph, transport or reshape the first pile into the second, and associate a "global" cost to every such transport, using the "local" consideration of how much it costs to move a grain of sand from one place to another. Recent years have witnessed the spread of OT in several fields, thanks to the emergence of approximate solvers that can scale to sizes and dimensions that are relevant to data sciences. Thanks to this newfound scalability, OT is being increasingly used to unlock various problems in imaging sciences (such as color or texture processing), computer vision and graphics (for shape manipulation) or machine learning (for regression, classification and density fitting). This short book reviews OT with a bias toward numerical methods and their applications in data sciences, and sheds lights on the theoretical properties of OT that make it particularly useful for some of these applications.